Neo & Byte · #1 · Quick sort

I Already Sorted It

Four-panel comic. Byte gives Quick Sort an array that is already in order. With the last value as pivot, every pass splits off a single value, and the receipt reads 499,500 comparisons for 1,000 values.

Transcript

  1. Panel 1. Byte: “I sorted it already, so this will be instant!”
  2. Panel 2. Quick Sort: “Pivot: the last one. Everyone else is smaller.” Quick Sort: “Right side: empty.”
  3. Panel 3. Quick Sort: “Pivot 7. Right side: empty. Pivot 6. Right side: empty…”
  4. Panel 4. Byte: “I was trying to help!” Quick Sort: “1,000 sorted values: 499,500 comparisons.”

Actually…

This quick sort takes the last value of each part as its pivot. On a sorted array that pivot is always the largest value, so every pass splits off only one value, and the sort makes about n²/2 comparisons, O(n²), instead of O(n log n) on average. A random pivot, or the median of the first, middle and last values, avoids this; insertion sort, by contrast, finishes a sorted array with n − 1 comparisons.

See it step by step

In the VisiGrab app, quick sort runs pivot by pivot, every comparison on screen, and shows why a sorted array is its worst case. App Store · Google Play