why quick sort when spill map output?
Hello forumers, Before spill the data in kvbuffer to local disk in map task, k/v are sorted using quick sort. The complexity of quick sort is O(nlogn) and worst case is O(n^2). Why using quick sort? Regards
Re: why quick sort when spill map output?
Sorting out of the map phase is core to how hadoop works. Are you asking why sort at all? or why did someone use quick sort as opposed to _sort? Cheers James On 2011-02-28, at 3:30 AM, elton sky wrote: > Hello forumers, > > Before spill the data in kvbuffer to local disk in map task, k/v are > sorted using quick sort. The complexity of quick sort is O(nlogn) and > worst case is O(n^2). > Why using quick sort? > > Regards
Re: why quick sort when spill map output?
one of the major reasons of using quicksort would be that quicksort can easily be parallalized...due to its divide and conquer nature On Mon, Feb 28, 2011 at 6:06 PM, James Seigel wrote: > Sorting out of the map phase is core to how hadoop works. Are you asking why > sort at all? or why did someone use quick sort as opposed to _sort? > > Cheers > James > > > On 2011-02-28, at 3:30 AM, elton sky wrote: > >> Hello forumers, >> >> Before spill the data in kvbuffer to local disk in map task, k/v are >> sorted using quick sort. The complexity of quick sort is O(nlogn) and >> worst case is O(n^2). >> Why using quick sort? >> >> Regards > >