Quicksorts vs. "Pipe Organ" Arrays
Channel: Musicombo
Date: 2020-07-23

Many of you have probably heard about Quicksort's O(n^2) worst-case behavior on arrays with "unfriendly" patterns or distributions. It turns out if you have the *same* data ascending in the first half of an array and descending in the second half, pivots in the middle, at the start, at the end, or chosen from a "median-of-three" scheme will be far away from the median. This so-called "pipe organ" distribution is very pathological to Quicksort, and even though Introsort switches to Heapsort to stay at O(n log n) worst-case, it still trips up and becomes stuck many, many times.

It also turns out that Orson Peters' new Pattern-Defeating Quicksort (or PDQSort) is a *huge* improvement over Introsort, and you should definitely check it out! https://github.com/orlp/pdqsort

Check out the program here: https://github.com/MusicTheorist/ArrayVisualizer
Visit the channel Discord here: https://discord.com/invite/2xGkKC2
Check out the Mother 1+2 Restoration project: https://discord.com/invite/ajQf9Ut