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 Colors
Dutch National Flag 3-pointermedium
2.Merge Intervals
Sort by start timemedium
3.Insert Interval
Interval overlap mergemedium
4.Meeting Rooms
Sort by start time + check overlapeasy
5.Meeting Rooms II
Min heap or sweep linemedium
6.3Sum
Sort + Two Pointersmedium
7.4Sum
Sort + Two Pointersmedium
8.Largest Number
Custom string comparator (a+b vs b+a)medium
9.Top K Frequent Elements
Bucket sort / Min heapmedium
10.Kth Largest Element in an Array
Quickselect / Min heapmedium
11.Merge Sorted Array
Three pointers from endeasy
12.Squares of a Sorted Array
Two pointers from endseasy
13.Non-overlapping Intervals
Sort by end time (Greedy)medium
14.Minimum Number of Arrows to Burst Balloons
Sort by end coordinatemedium
15.Relative Sort Array
Counting sort / Map rankeasy
16.Sort Characters By Frequency
Bucket sort / Frequency mapmedium
17.H-Index
Sort descending or Counting arraymedium
18.Maximum Gap
Bucket sort / Pigeonhole principlehard

Also Important

10 more questions worth practicing.

19.Sort an Array
Merge sort / Quicksort / Heapsortmedium
20.Custom Sort String
Custom char priority mapmedium
21.Reorder Data in Log Files
Custom string tie-breaker sortmedium
22.Queue Reconstruction by Height
Sort by height desc, k ascmedium
23.Minimum Difference Between Highest and Lowest of K Scores
Sort + fixed window Keasy
24.Find K Closest Elements
Sort by abs difference / Binary searchmedium
25.Rank Transform of an Array
Sort + Unique rank mapeasy
26.Boats to Save People
Sort + Two Pointersmedium
27.Maximum Units on a Truck
Sort by units per box desceasy
28.Minimum Moves to Equal Array Elements II
Sort + 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 lexicographically

Custom 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²) worst

Choose 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."