Pattern #9
Sorting
Important interview questions, thinking patterns, sorting algorithms, and rules for solving sorting problems in Go.
Must Solve
18 core questions โ solve these first.
- 1.Sort ColorsDutch National Flag 3-pointermedium
- 2.Merge IntervalsSort by start timemedium
- 3.Insert IntervalInterval overlap mergemedium
- 4.Meeting RoomsSort by start time + check overlapeasy
- 5.Meeting Rooms IIMin heap or sweep linemedium
- 6.3SumSort + Two Pointersmedium
- 7.4SumSort + Two Pointersmedium
- 8.Largest NumberCustom string comparator (a+b vs b+a)medium
- 9.Top K Frequent ElementsBucket sort / Min heapmedium
- 10.Kth Largest Element in an ArrayQuickselect / Min heapmedium
- 11.Merge Sorted ArrayThree pointers from endeasy
- 12.Squares of a Sorted ArrayTwo pointers from endseasy
- 13.Non-overlapping IntervalsSort by end time (Greedy)medium
- 14.Minimum Number of Arrows to Burst BalloonsSort by end coordinatemedium
- 15.Relative Sort ArrayCounting sort / Map rankeasy
- 16.Sort Characters By FrequencyBucket sort / Frequency mapmedium
- 17.H-IndexSort descending or Counting arraymedium
- 18.Maximum GapBucket sort / Pigeonhole principlehard
Also Important
10 more questions worth practicing.
- 19.Sort an ArrayMerge sort / Quicksort / Heapsortmedium
- 20.Custom Sort StringCustom char priority mapmedium
- 21.Reorder Data in Log FilesCustom string tie-breaker sortmedium
- 22.Queue Reconstruction by HeightSort by height desc, k ascmedium
- 23.Minimum Difference Between Highest and Lowest of K ScoresSort + fixed window Keasy
- 24.Find K Closest ElementsSort by abs difference / Binary searchmedium
- 25.Rank Transform of an ArraySort + Unique rank mapeasy
- 26.Boats to Save PeopleSort + Two Pointersmedium
- 27.Maximum Units on a TruckSort by units per box desceasy
- 28.Minimum Moves to Equal Array Elements IISort + Median targetmedium
How to Think
- Need order first?Sort
- Need pair/triplet?Sort + Two Pointers
- Intervals?Sort by start time
- Need smallest / largest K?Sort or Heap
- Need greedy choice?Sort โ Pick best next item
- Need duplicate values together?Sort them
Go Thinking & Reference
Basic Built-in Sorting
sort.Ints(nums) // Sort slice of ints ascending
sort.Strings(words) // Sort slice of strings lexicographicallyCustom Comparator (sort.Slice)
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].Start < intervals[j].Start // return true means i comes before j
})๐ Built-in sort uses Pattern-defeating Quicksort (pdqsort): O(n log n)
Main Sorting Algorithms
Bubble Sort
O(nยฒ)Compare neighbors โ Swap if wrong order. Repeat passes until sorted.
๐ Simple, but usually too slow.
Selection Sort
O(nยฒ)Find min โ Place at start. Find next min โ Place next.
๐ Select the next correct value.
Insertion Sort
O(nยฒ)Build sorted part one item at a time by shifting elements.
๐ Good when data is small or almost sorted.
Merge Sort
O(n log n)Divide into halves recursively โ Sort halves โ Merge in order. (Space: O(n))
๐ Divide โ Sort โ Merge.
Quick Sort
O(n log n) avg | O(nยฒ) worstChoose pivot โ Partition elements (smaller < pivot < bigger) โ Recurse.
๐ Pivot and partition.
Stable vs Unstable Sorting
Stable sorting means equal values keep their original relative order.
Alice score 90
Bob score 90
After stable sort by score:
Alice
Bob (original relative order stays)๐ก Stable matters when sorting by multiple fields (e.g. sort by name first, then by score).
Interview Rules
- 1. Pair/triplet problem? โ Consider Sort + Two Pointers
- 2. Intervals? โ Usually sort by start time first
- 3. Need ordering? โ Sort
- 4. Need K largest/smallest? โ Sort or Heap
- 5. Need duplicates together? โ Sort
- 6. Need binary search? โ Data must be sorted
- 7. Need greedy choice? โ Sorting often comes first
- 8. Need to preserve original index? โ Store index before sorting
- 9. General good sorting โ
O(n log n) - 10. Avoid O(nยฒ) sorting for large inputs
Small Rules
- Rule 1: Sorting costs O(n log n). If it makes the rest easy, it is worth it.
- Rule 2: Sorted data unlocks Two Pointers, Binary Search, Greedy, and Interval Merging.
- Rule 3:Don't use Bubble Sort in production for large data (100k items = 10 billion comparisons).
- Rule 4: If order must stay unchanged, attach original index before sorting.
- Rule 5: Interviewers care more about WHAT you sort by (custom comparators) than writing sort from scratch.
Production Thinking
Database Results โ ORDER BY created_at DESC (Prefer DB index over app memory sort)
Logs Merging โ Sort by timestamp to merge multi-server logs
Job Scheduling โ Sort by priority / deadline / start time
E-commerce โ Custom comparator for price, rating, popularity
Interval Systems โ Sort meetings by start time to detect overlaps
What Should You Actually Remember?
Bubble / Insertion โ understand only
Merge Sort โ know properly (Split + Merge)
Quick Sort โ know properly (Pivot + Partition)
Built-in sorting โ use confidently (sort.Slice)Remember This
Need order โ Sort
Pair / Triplet โ Sort + Two Pointers
Intervals โ Sort by start time
K largest/smallest โ Sort / Heap
Merge sorted data โ Two Pointers
General efficient โ O(n log n)
Merge Sort โ Split + Merge
Quick Sort โ Pivot + Partition๐ก Golden Rule: "Sorting may cost O(n log n), but the order it creates can make the whole problem much easier."