Merge Sort
Merge sort is a stable, comparison-based sorting algorithm that uses the divide-and-conquer paradigm to sort elements in $O(n \log n)$ time.
Algorithm Overview
Divide and Conquer Strategy
- Divide: Split array into two halves
- Conquer: Recursively sort each half
- Combine: Merge the two sorted halves
Mathematical Formulation
$$ \text{MergeSort}(A, \text{left}, \text{right}) = \begin{cases} A & \text{if left} \geq \text{right} \\ \text{Merge}(\text{MergeSort}(A, \text{left}, \text{mid}), \text{MergeSort}(A, \text{mid}+1, \text{right})) & \text{otherwise} \end{cases} $$
where: $$ \text{mid} = \lfloor (\text{left} + \text{right}) / 2 \rfloor $$
Visualization
Merge Operation
The key operation that combines two sorted subarrays into one sorted array.
Process
Given two sorted arrays $L[0 \ldots n_1-1]$ and $R[0 \ldots n_2-1]$:
- Compare $L[i]$ and $R[j]$
- Copy smaller element to result
- Advance pointer of array from which element was copied
- Repeat until one array is exhausted
- Copy remaining elements from non-empty array
Go Implementation: Merge Function
1// merge combines two sorted subarrays
2func merge(arr []int, left, mid, right int) {
3 // Create temporary arrays
4 n1 := mid - left + 1
5 n2 := right - mid
6
7 L := make([]int, n1)
8 R := make([]int, n2)
9
10 // Copy data to temp arrays
11 copy(L, arr[left:mid+1])
12 copy(R, arr[mid+1:right+1])
13
14 // Merge temp arrays back
15 i, j, k := 0, 0, left
16
17 for i < n1 && j < n2 {
18 if L[i] <= R[j] {
19 arr[k] = L[i]
20 i++
21 } else {
22 arr[k] = R[j]
23 j++
24 }
25 k++
26 }
27
28 // Copy remaining elements
29 for i < n1 {
30 arr[k] = L[i]
31 i++
32 k++
33 }
34
35 for j < n2 {
36 arr[k] = R[j]
37 j++
38 k++
39 }
40}
Time: $O(n_1 + n_2)$ where $n_1, n_2$ are sizes of subarrays
Space: $O(n_1 + n_2)$ for temporary arrays
Complexity Analysis
Time Complexity
Recurrence relation: $$ T(n) = 2T(n/2) + O(n) $$
Solution (by Master Theorem, case 2): $$ T(n) = O(n \log n) $$
Proof by recursion tree:
- Height of tree: $\log_2 n$
- Work at each level: $O(n)$
- Total work: $O(n) \times O(\log n) = O(n \log n)$
All cases: Best, Average, Worst = $O(n \log n)$
Space Complexity
Recursive call stack: $O(\log n)$
Temporary arrays: $O(n)$
Total: $O(n)$
Array Implementation
Top-Down (Recursive)
1// MergeSort sorts array using top-down merge sort
2func MergeSort(arr []int) {
3 if len(arr) <= 1 {
4 return
5 }
6 mergeSortHelper(arr, 0, len(arr)-1)
7}
8
9func mergeSortHelper(arr []int, left, right int) {
10 if left >= right {
11 return
12 }
13
14 mid := left + (right-left)/2
15
16 // Recursively sort both halves
17 mergeSortHelper(arr, left, mid)
18 mergeSortHelper(arr, mid+1, right)
19
20 // Merge sorted halves
21 merge(arr, left, mid, right)
22}
23
24// Example
25func main() {
26 arr := []int{38, 27, 43, 3, 9, 82, 10}
27 fmt.Println("Before:", arr)
28 MergeSort(arr)
29 fmt.Println("After:", arr)
30 // Output: [3, 9, 10, 27, 38, 43, 82]
31}
Space: $O(n + \log n) = O(n)$
Bottom-Up (Iterative)
1// MergeSortIterative sorts using bottom-up approach
2func MergeSortIterative(arr []int) {
3 n := len(arr)
4
5 // Start with subarrays of size 1, double size each iteration
6 for size := 1; size < n; size *= 2 {
7 // Pick starting index of left subarray
8 for left := 0; left < n-size; left += 2 * size {
9 mid := left + size - 1
10 right := min(left+2*size-1, n-1)
11
12 merge(arr, left, mid, right)
13 }
14 }
15}
16
17func min(a, b int) int {
18 if a < b {
19 return a
20 }
21 return b
22}
23
24// Example
25func main() {
26 arr := []int{38, 27, 43, 3, 9, 82, 10}
27 fmt.Println("Before:", arr)
28 MergeSortIterative(arr)
29 fmt.Println("After:", arr)
30 // Output: [3, 9, 10, 27, 38, 43, 82]
31}
Iterations: $\lceil \log_2 n \rceil$
Space: $O(n)$ (no recursion stack)
Linked List Implementation
Merge sort is particularly efficient for linked lists because:
- No random access needed
- Merge operation is $O(1)$ space
- No need for auxiliary arrays
Go Implementation for Linked Lists
1type ListNode struct {
2 Val int
3 Next *ListNode
4}
5
6// MergeSortList sorts a linked list using merge sort
7func MergeSortList(head *ListNode) *ListNode {
8 if head == nil || head.Next == nil {
9 return head
10 }
11
12 // Find middle using slow/fast pointers
13 slow, fast := head, head
14 var prev *ListNode
15
16 for fast != nil && fast.Next != nil {
17 prev = slow
18 slow = slow.Next
19 fast = fast.Next.Next
20 }
21
22 // Split list into two halves
23 prev.Next = nil
24
25 // Recursively sort both halves
26 left := MergeSortList(head)
27 right := MergeSortList(slow)
28
29 // Merge sorted halves
30 return mergeLists(left, right)
31}
32
33// mergeLists merges two sorted linked lists
34func mergeLists(l1, l2 *ListNode) *ListNode {
35 dummy := &ListNode{}
36 curr := dummy
37
38 for l1 != nil && l2 != nil {
39 if l1.Val <= l2.Val {
40 curr.Next = l1
41 l1 = l1.Next
42 } else {
43 curr.Next = l2
44 l2 = l2.Next
45 }
46 curr = curr.Next
47 }
48
49 if l1 != nil {
50 curr.Next = l1
51 } else {
52 curr.Next = l2
53 }
54
55 return dummy.Next
56}
57
58// Example
59func main() {
60 // Create list: 4 -> 2 -> 1 -> 3
61 head := &ListNode{Val: 4}
62 head.Next = &ListNode{Val: 2}
63 head.Next.Next = &ListNode{Val: 1}
64 head.Next.Next.Next = &ListNode{Val: 3}
65
66 sorted := MergeSortList(head)
67 // Result: 1 -> 2 -> 3 -> 4
68}
Time: $O(n \log n)$
Space: $O(\log n)$ for recursion stack only (no auxiliary arrays!)
Comparison: Array vs. Linked List
| Aspect | Array | Linked List |
|---|---|---|
| Time | $O(n \log n)$ | $O(n \log n)$ |
| Auxiliary Space | $O(n)$ | $O(1)$ |
| Find Middle | $O(1)$ | $O(n)$ |
| Merge | $O(n)$ with copying | $O(n)$ pointer manipulation |
| Cache Performance | Better (contiguous) | Worse (scattered) |
| Preferred | Arrays | Linked Lists |
Properties
Stability
Merge sort is stable: equal elements maintain their relative order.
Proof: During merge, when $L[i] = R[j]$, we take from $L$ first (left subarray), preserving original order.
Adaptivity
Merge sort is not adaptive: doesn't take advantage of existing order.
Time is always $O(n \log n)$, even if array is already sorted.
In-Place
Standard merge sort is not in-place: requires $O(n)$ auxiliary space.
Note: In-place variants exist but are complex and lose stability.
Optimizations
1. Use Insertion Sort for Small Subarrays
1const INSERTION_THRESHOLD = 10
2
3func mergeSortOptimized(arr []int, left, right int) {
4 if right - left <= INSERTION_THRESHOLD {
5 insertionSort(arr, left, right)
6 return
7 }
8
9 mid := left + (right-left)/2
10 mergeSortOptimized(arr, left, mid)
11 mergeSortOptimized(arr, mid+1, right)
12 merge(arr, left, mid, right)
13}
14
15func insertionSort(arr []int, left, right int) {
16 for i := left + 1; i <= right; i++ {
17 key := arr[i]
18 j := i - 1
19 for j >= left && arr[j] > key {
20 arr[j+1] = arr[j]
21 j--
22 }
23 arr[j+1] = key
24 }
25}
Improvement: 10-15% faster in practice.
2. Check if Already Sorted
1func mergeSortWithCheck(arr []int, left, right int) {
2 if left >= right {
3 return
4 }
5
6 mid := left + (right-left)/2
7
8 mergeSortWithCheck(arr, left, mid)
9 mergeSortWithCheck(arr, mid+1, right)
10
11 // If already sorted, skip merge
12 if arr[mid] <= arr[mid+1] {
13 return
14 }
15
16 merge(arr, left, mid, right)
17}
Best case improvement: $O(n)$ for already sorted arrays.
Comparison with Other Sorting Algorithms
| Algorithm | Time (Best) | Time (Avg) | Time (Worst) | Space | Stable | Adaptive |
|---|---|---|---|---|---|---|
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | No |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | No |
| Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | No | No |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes |
| Tim Sort | $O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | Yes |
Applications
1. External Sorting
When data doesn't fit in memory (e.g., sorting large files on disk).
Reason: Sequential access pattern is disk-friendly.
Process:
- Sort chunks that fit in memory
- Merge sorted chunks using k-way merge
2. Inversion Count
Count number of pairs $(i, j)$ where $i < j$ but $A[i] > A[j]$.
1func countInversions(arr []int) int {
2 temp := make([]int, len(arr))
3 return mergeSortAndCount(arr, temp, 0, len(arr)-1)
4}
5
6func mergeSortAndCount(arr, temp []int, left, right int) int {
7 count := 0
8 if left < right {
9 mid := left + (right-left)/2
10
11 count += mergeSortAndCount(arr, temp, left, mid)
12 count += mergeSortAndCount(arr, temp, mid+1, right)
13 count += mergeAndCount(arr, temp, left, mid, right)
14 }
15 return count
16}
17
18func mergeAndCount(arr, temp []int, left, mid, right int) int {
19 i, j, k := left, mid+1, left
20 count := 0
21
22 for i <= mid && j <= right {
23 if arr[i] <= arr[j] {
24 temp[k] = arr[i]
25 i++
26 } else {
27 temp[k] = arr[j]
28 count += (mid - i + 1) // All remaining in left are inversions
29 j++
30 }
31 k++
32 }
33
34 for i <= mid {
35 temp[k] = arr[i]
36 i++
37 k++
38 }
39
40 for j <= right {
41 temp[k] = arr[j]
42 j++
43 k++
44 }
45
46 copy(arr[left:right+1], temp[left:right+1])
47 return count
48}
Time: $O(n \log n)$
3. Linked List Sorting
Merge sort is the preferred algorithm for linked lists.
Reason: $O(1)$ space, no random access needed.
4. Stable Sorting Requirement
When stability is required and $O(n)$ space is acceptable.
Examples: Sorting records by multiple keys.
When to Use Merge Sort
✅ Use when:
- Need guaranteed $O(n \log n)$ performance
- Stability is required
- Sorting linked lists
- External sorting (large datasets on disk)
- Parallel sorting
- Space is not a constraint
❌ Don't use when:
- Memory is severely limited (use heap sort or in-place quick sort)
- Data is small (use insertion sort)
- Average case $O(n \log n)$ with $O(\log n)$ space is acceptable (use quick sort)
- Need adaptive behavior (use tim sort or insertion sort)
Common Interview Problems
1. Sort Linked List
Problem: Sort a linked list in $O(n \log n)$ time and $O(1)$ space.
Solution: Merge sort with slow/fast pointer to find middle.
2. Count Inversions
Problem: Count pairs where $i < j$ but $A[i] > A[j]$.
Solution: Modified merge sort counting inversions during merge.
3. Merge K Sorted Arrays
Problem: Merge $k$ sorted arrays into one sorted array.
Solution: K-way merge using min-heap.
Time: $O(n \log k)$ where $n$ is total elements.
4. Reverse Pairs
Problem: Count pairs where $i < j$ and $A[i] > 2 \times A[j]$.
Solution: Modified merge sort with additional counting step.
Related Snippets
- Binary Search
Binary search is an efficient algorithm for finding a target value in a sorted … - Binary Tree
A binary tree is a tree data structure where each node has at most two children, … - General Tree
A tree is a hierarchical data structure consisting of nodes connected by edges, … - Heap Data Structure
A heap is a specialized tree-based data structure that satisfies the heap … - Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data … - Linked List Operations
Optimal techniques for common linked list operations using pointer manipulation, … - LRU and LFU Cache
Cache replacement policies determine which items to evict when the cache is … - Quadtree
A Quadtree is a tree data structure where each internal node has exactly four … - Quick Sort
Quick sort is an efficient, in-place, comparison-based sorting algorithm that … - String Similarity Algorithms
Algorithms for measuring similarity between strings, used in spell checking, DNA … - Terrain & Heightmap Generation
Procedural terrain generation creates realistic landscapes using mathematical … - Trie (Prefix Tree)
A Trie (pronounced "try") is a tree-like data structure used to store … - Wave Function Collapse
Wave Function Collapse (WFC) is a procedural generation algorithm that creates …