Follow-up to sorting question from user meeting

[Nathan Fiedler <na...@gmail.com>]

In yesterday's user group meeting, Ted asked if the new sort function
in the MapReduce implementation was stable, since typically quicksort
is not stable for efficient implementations. Assuming Hadoop is using
one of the sort() methods in java.util.Arrays based on quicksort, then
there is a very high likelihood that the sort is not stable. Those
sort() methods explain that the implementation is based on Jon L.
Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
1993). Looking at that document
(http://citeseer.ist.psu.edu/bentley93engineering.html) it's clear
their algorithm is not stable.

What this means to MapReduce is not clear to me, but I wanted to
provide the follow-up since no one in the meeting knew the answer off
the top of their head.

BTW, thanks for a really enjoyable user group meeting. I'm looking
forward to the next one.

n