Interactive Lab · DSA & Algorithms
Ask "which sort is fastest?" in an interview and the right answer is "on what input?". Here insertion sort (O(n²)), merge sort (O(n log n), always) and quicksort (O(n log n) on average, O(n²) worst) race on the exact same array. Every tick, each one does one operation: a comparison or an array write. Whoever needs the fewest operations finishes first. Flip the input to nearly-sorted and watch the "slow" sort win. Flip it to sorted and watch quicksort fall over.
▶ The playground, pick an input, then start the race
Each lane is one algorithm sorting its own copy of the same array. Blue bars are the two values being compared; the orange bar was just written. The thin bar under each name is its progress. A lane turns green when it's sorted.
input shape
quicksort pivot
Real-world sorts are hybrids built from exactly this race. Python's sorted() and Java's object sort use Timsort: merge sort that spots already-sorted runs and uses insertion sort on small pieces, because you just saw insertion win on nearly-ordered data. C++'s std::sort is introsort: quicksort that switches to heapsort when recursion gets too deep, which is the sorted-input collapse you can trigger above. Interviewers ask "which sort would you use and why?" to see if you think about the input, not just the Big-O table.
The code that's actually running, every comparison and write is counted
Set the size to 100 and the shape to nearly-sorted. Predict before you race: insertion sort is "the O(n²) one", so surely it comes last? Then switch to already sorted with the naive last-element pivot: does quicksort still beat insertion? Race both, read the ops column, then flip the pivot to random and race sorted again. Which algorithm's op count barely moves no matter which shape you pick?
The takeaway
O(n²) in the worst case, but its cost is really n + (number of out-of-order pairs). On nearly-sorted input that's close to n, and it beats both n log n sorts.n log₂ n work on every shape, sorted, reversed or random. Predictable, stable, but it needs O(n) extra memory for merging.n log n). The last element of a sorted array is the maximum, so every split peels off one element: n(n−1)/2 comparisons and recursion n levels deep. A random pivot fixes it.