Part III · Searching, Sorting and Selection
18. Efficient and Specialized Sorting
9 lessons•46 topics•Beginner / Intermediate
9 of 9 lessons published
18.012 animated
Merge sort
- Divide and conquer
- Merge procedure
- Stable sorting
- Temporary arrays
- Bottom-up merge sort
- Linked list merge sort
18.022 animated
Quick sort
- Partition schemes Lomuto/Hoare
- Pivot selection
- Randomized pivot
- Three-way partition
- Worst-case O(n²)
- Tail recursion
18.031 animated
Heap sort
- Heapify
- Build heap
- Repeated extract maximum
- In-place property
- Instability
18.041 animated
Counting sort
- Bounded integer domain
- Frequency and prefix counts
- Stable output
- Negative keys offset
- Complexity
18.051 animated
Radix sort
- LSD vs MSD
- Digit buckets
- Stable passes
- Integers vs strings
- Base selection
18.061 animated
Bucket sort
- Distribution assumptions
- Bucket construction
- In-bucket sort
- Expected complexity
18.07Lesson
Hybrid and library sorting
- Insertion sort threshold
- Introsort
- TimSort
- Java primitive sort
- Java object sort
- Parallel sort
18.081 animated
External sorting
- External merge sort
- Runs
- K-way merge
- Disk I/O
- Sorting beyond RAM
18.091 animated
Lower bounds and variants
- Comparison lower bound Ω(n log n)
- Sorting networks intro
- Stable partition
- Parallel merge sort