Thanks for your detail description. My question should be more specific to quicksort part. This line <https://github.com/apache/incubator-impala/blob/master/be/src/runtime/sorter.cc#L1258> say recurse on the small partition due to stack consideration, while as my understanding quicksort should recurse on both left partition and right partition, so I'm curious how it keep one run sorted, does it sort in later merge sort or somewhere else? But the merge process should take sorted runs as input.
2017-08-05 0:18 GMT+08:00 Tim Armstrong <tarmstr...@cloudera.com>: > The Sorter does a 3-level hybrid sort with merge sort, quicksort and > insertion sort. > > SortHelper implements a 2-level hybrid in-memory sort. It fully sorts an > arbitrarily sized in-memory input. E.g. if 'begin' and 'end' point to the > begin and end of the sorted run, it will sort the full run. It does > quicksort recursively then switches to insertion sort once the partitions > are less than INSERTION_THRESHOLD = 16. > > Sorter also supports an external merge sort - if the full input doesn't fit > in memory, it sorts in-memory runs with SortHelper() then does merge sort > with the sorted runs. > > On Thu, Aug 3, 2017 at 11:13 PM, 俊杰陈 <cjjnj...@gmail.com> wrote: > > > Hi > > I'm looking Sorter.cc and found that Sorter::SortHelper just sort smaller > > partition. Is there anything I missed? > > > > -- > > Thanks & Best Regards > > > -- Thanks & Best Regards
