[IMPALA-9958] Implement Introsort by adding a heapsort case

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Won't Do
• Component/s: Backend
• Epic Color: ghx-label-14
• Assignee: Unassigned
• Reporter: Shant Hovsepian
• Created: 15/Jul/20 14:25
• Updated: 09/Jan/21 02:06
• Resolved: 09/Jan/21 02:06

Description

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.