Powersort

Powersort is an adaptive sorting algorithm designed to optimally exploit existing order in the input data with minimal overhead. Powersort is the default list-sorting algorithm in CPython since version 3.11 and is also used in NumPy , PyPy, AssemblyScript , and Apple's WebKit . Powersort belongs to the family of merge sort algorithms. More specifically, Powersort builds on Timsort; it is a drop-in replacement for Timsort's suboptimal heuristic merge policy. Unlike Timsort, Powersort is derived from first principles (see connection to nearly optimal binary search trees) and offers strong performance guarantees. Like Timsort, Powersort is stable and comparison-based. This property is essential for many applications. Powersort was proposed by J. Ian Munro and Sebastian Wild.

Powersort is an adaptive sorting algorithm designed to optimally exploit existing order in the input data with minimal overhead. Powersort is the default list-sorting algorithm in CPython since version 3.11 and is also used in NumPy , PyPy, AssemblyScript , and Apple's WebKit . Powersort belongs to the family of merge sort algorithms. More specifically, Powersort builds on Timsort; it is a drop-in replacement for Timsort's suboptimal heuristic merge policy. Unlike Timsort, Powersort is derived from first principles (see connection to nearly optimal binary search trees) and offers strong performance guarantees. Like Timsort, Powersort is stable and comparison-based. This property is essential for many applications. Powersort was proposed by J. Ian Munro and Sebastian Wild. S := stack of runs // capacity ⌈lg(n)⌉ + 1 b 1 := 0; e 1 := FirstRunOf(A[b 1 ..n)) // A[b 1 ..e 1 ) is leftmost run while e 1 2 := e 1 + 1; e 2 := FirstRunOf(A[b 2 ..n)) // A[b 2 ..e 2 ) next run P := NodePower(n, b 1 , e 1 , b 2 , e 2 ) while S.top().power > P (b 1 , e 1 ) := Merge(S.pop(), A[b 1 ..e 1 )) end while S.push((A[b 1 , e 1 ), P)); b 1 := b 2 ; e 1 := e 2 end while // Now A[b 1 ..e 1 ) is the rightmost run while ¬S.empty() (b 1 , e 1 ) := Merge(S.pop(), A[b 1 ..e 1 )) end while algorithm NodePower(n, b 1 , e 1 , b 2 , e 2 ) n 1 := e 1 − b 1 ; n 2 := e 2 − b 2 ; a := (b 1 + n 1 /2)/n; b := (b 2 + n 2 /2)/n p := 0 while ⌊a · 2 p ⌋ == ⌊b · 2 p ⌋ p := p + 1 end while return p The implementation of Merge is inherited from TimSort and includes the "galloping" heuristic. Powersort simultaneously removes all of these limitations. Despite its advanced theoretical foundation, its analysis is much easier, and it provably never uses more than n\mathcal{H} +O(n) comparisons, where \mathcal{H} = \sum_{i=1}^{r} \frac{\ell_i}{n} \log_2\left({\frac n{\ell_i}}\right) , for \ell_1,\ldots,\ell_r the lengths of the runs in the input. Powersort has been shown to outperform Timsort by up to 30% on certain types of input data that contain long runs of sorted elements. Powersort has further been extended to multiway merging, something that was not possible with Timsort. S := empty stack // capacity (k − 1)⌈log k (n) + 1⌉ b 1 := 0; e 1 = FirstRunOf(A[b 1..n )) while e 1 2 := e 1 ; e 2 := FirstRunOf(A[b 2..n )) P := Power k (n, b 1 , e 1 , b 2 , e 2 ) while S.top().power > P P':= S.top().power L := empty list; L.append(S.pop()) while S.top().power == P′ L.append(S.pop()) end while // merge runs in L with A[b 1 ..e 1 ) (b 1 , e 1 ) := Merge(L, A[b 1 ..e 1 )) end while S.push((A[b 1 , e 1 ), P)) b 1 := b 2 ; e 1 := e 2 end while // Now A[b 1 ..e 1 ) is the rightmost run while ¬S.empty() // pop (up to) k − 1 runs, merge with A[b 1 ..e 1 ) (b 1 , e 1 ) := Merge(S.pop(k − 1), A[b 1 ..e 1 )) end while algorithm Power k (n, b 1 , e 1 , b 2 , e 2 ) n 1 := e 1 − b 1 ; n 2 := e 2 − b 2 ; p := 0 a := (b 1 + n 1 /2)/n; b := (b 2 + n 2 /2)/n while ⌊a · k p ⌋ == ⌊b · k p ⌋ p := p + 1 end while return p A more graphical approach to explaining Powersort is used in Sebastian Wild's PyCon US 2023 talk.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372793346 under CC BY-SA 4.0; modifications have been made.