Comparison Sorts & The n log n Bound

Merge sort, quicksort, heapsort, and insertion sort compared, the n log n lower bound, and introsort.

0 / 4 solved

Question Tags Difficulty Success

1. One Pass Of Lomuto

quicksortpartition +1

Medium —

2. The Half That Vanished

mergesortdebugging +1

Medium —

3. Twenty Nine Comparisons

lower-bounddecision-tree +1

Medium —

4. Skipping The Equal Keys

quicksortduplicate-keys +2

Hard —

Learning Resources

Algorithms, 4th Edition, Quicksort

Algorithms, 4th Edition, Mergesort and the lower bound

CMU 15-122, Quicksort and partitioning

MIT 6.006 Lecture 3, Sorting

Up next

4 of 4 questions here are still unsolved.

Next module Counting, Radix & Bucket Sort