[
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.
