hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Chris Douglas (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HADOOP-3442) QuickSort may get into unbounded recursion
Date Mon, 09 Jun 2008 04:19:45 GMT

    [ https://issues.apache.org/jira/browse/HADOOP-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12603468#action_12603468

Chris Douglas commented on HADOOP-3442:

bq. what's the complexity in time/space of BatcherSort

It takes O(n*log\(n)^2) time; without executing any of its stages in parallel, it's probably
not worth using in practice before the alternatives, but it's as fast as QuickSort for small
data sets.

bq. For HeapSort, there is a o.a.h.u.PriorityQueue. Could we use that?

I don't think it would be an improvement. HeapSort effects the sort in-place, while using
PriorityQueue would require additional allocations and several unnecessary abstractions. HeapSort
isn't a full heap implementation, either, so I'd argue that it's not adding redundant code.

> QuickSort may get into unbounded recursion
> ------------------------------------------
>                 Key: HADOOP-3442
>                 URL: https://issues.apache.org/jira/browse/HADOOP-3442
>             Project: Hadoop Core
>          Issue Type: Bug
>          Components: mapred
>    Affects Versions: 0.17.0
>            Reporter: Runping Qi
>            Assignee: Chris Douglas
>            Priority: Blocker
>             Fix For: 0.17.1, 0.18.0
>         Attachments: 3442-0.patch, 3442-0v17.patch, 3442-1.patch, CheckSortBuffer.java,
HADOOP-3442.patch, overflow.zip, spillbuffers.patch

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message