Sorting Algorithms

Source: Sorting patterns from Ace the Data Science Interview — Chapter 9 (Huo & Singh), expanded with original labs and animations for this course.

Implement the classics, state their tradeoffs in writing, and watch each step color a grid. Open the visualizer, pick an algorithm + array, then step through comparisons / swaps / pivots.

Live animation

Cells light up as compare (amber), swap/move (red), write (blue), pivot (purple), or sorted (green). Height scales with value.

Complexity tradeoffs (memorize the story)

Sort	Best	Average	Worst	Extra space	Stable?	Notes
Bubble	$O(N)$*	$O(N^2)$	$O(N^2)$	$O(1)$	Yes	*with early-exit flag
Selection	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	No	Min swaps; simple
Insertion	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$	Yes	Fast on nearly sorted
Mergesort	$O(N\log N)$	$O(N\log N)$	$O(N\log N)$	$O(N)$	Yes	Predictable; great for external sort
Quicksort	$O(N\log N)$	$O(N\log N)$	$O(N^2)$	$O(\log N)$ stack	No*	*naive Lomuto; randomize pivot
Heapsort	$O(N\log N)$	$O(N\log N)$	$O(N\log N)$	$O(1)$	No	In-place guaranteed bound

*Practical libraries use introsort / timsort hybrids — interviews still want the textbook cores.

Quiz

Sorting (harder)

1 / 6

Which pair is typically stable + O(N log N) worst-case?

Pick an answer to see if you are right.

Written resolutions

0/3 solved

Pick a sort

Using “stable” and “memory”, explain:

Interview: “Sort 50M records by key; equal keys must keep input order; RAM is tight but you can afford an O(N) buffer.” Which textbook sort do you pitch and why? Mention one you would reject.

Minimum 50 words. Your answer must include: “stable”, “memory”.

0 words/ 50 min

Meet the writing requirements, then you can open the model answer.

Sample walkthroughs (match the visualizer)

Bubble on [5,2,8,1]: compare/swap adjacent until the max sinks right each pass.

Selection: for i=0..n-2, find min in a[i..], swap into i.

Insertion: for i=1..n-1, slide a[i] left into the sorted prefix.

Mergesort: split [5,2,8,1] → [5,2]|[8,1] → singles → merge to [2,5]|[1,8] → [1,2,5,8].

Quicksort (Lomuto): pivot last element; grow a < pivot region; place pivot; recurse.

Heapsort: sift into a max-heap; swap a[0] with end; shrink; sift-down.

Implement six sorts

Input for each lab: n then n ints. Output: sorted ascending, space-separated. Do not call sorted / list.sort / std::sort — implement the algorithm named in the title.

C++ mergesort (same I/O)

Prev: Algorithms · Next: Coding Easy.