Shant Hovsepian created IMPALA-9958:
---------------------------------------
Summary: Implement Introsort by adding a heapsort case
Key: IMPALA-9958
URL: https://issues.apache.org/jira/browse/IMPALA-9958
Project: IMPALA
Issue Type: Improvement
Components: Backend
Reporter: Shant Hovsepian
Introsort is the standard hybrid sort implementation
[https://en.wikipedia.org/wiki/Introsort] which chooses between quicksort,
heapsort, and insertion sort given the current sort run size.
Currently the Sorter uses quicksort with insertion sort for batches smaller
than 16. With introsort in cases where the quisksort partitions the data above
a threshold 2*log(N), then the algorithm switches to using heapsort.
This should help mitigate worse case pivot selections.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
