👋 Welcome Gophers! In this lesson, we are going to explore how the merge sort algorithm works and why it’s much more efficient than the simple sorting algorithms we’ve seen so far.
How Merge Sort Works
Merge sort is an efficient, general-purpose, comparison-based sorting algorithm that uses a divide-and-conquer approach. Instead of repeatedly comparing adjacent elements like bubble sort or insertion sort, merge sort divides the array into smaller pieces, sorts those pieces, and then merges them back together.
The basic process is:
- Divide: Split the array into two halves
- Conquer: Recursively sort each half
- Merge: Combine the two sorted halves into a single sorted array
Here’s how it works conceptually with an example array [5, 2, 4, 3, 1]:
[5, 2, 4, 3, 1]
↓
Split
↓
[5, 2, 4] and [3, 1]
↓
Split
↓
[5], [2, 4], [3], [1]
↓
Split
↓
[5], [2], [4], [3], [1]
↓
Merge
↓
[2, 5], [4], [1, 3]
↓
Merge
↓
[2, 4, 5], [1, 3]
↓
Merge
↓
[1, 2, 3, 4, 5]
The Merge Process
When merging two sorted arrays, we compare the first elements of each array and take the smaller one. We continue this process until both arrays are empty:
- Compare 2 and 3, take 2
- Compare 5 and 3, take 3
- Compare 5 and 1, take 1
- No elements left in second array, add remaining 5
Time and Space Complexity
- Best Case: O(n log n) - even on already sorted data, we still divide and merge
- Average Case: O(n log n) - consistent performance
- Worst Case: O(n log n) - guaranteed performance
- Space Complexity: O(n) - requires temporary arrays during merging
This guaranteed O(n log n) performance is why merge sort is so popular for large datasets, despite requiring extra space.
Visual Representation
Here’s a visual representation of how merge sort divides and merges:
<svg viewBox="0 0 700 450" xmlns="http://www.w3.org/2000/svg" style="background-color: #1a1a1a; font-family: monospace;">
<!-- Title -->
<text x="350" y="25" fill="#e0e0e0" font-size="16" text-anchor="middle" font-weight="bold">Merge Sort: Divide Phase</text>
<!-- Level 0: Original array -->
<g id="level0">
<text x="20" y="55" fill="#888" font-size="12">Level 0:</text>
<rect x="80" y="40" width="35" height="35" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="97" y="62" fill="#fff" text-anchor="middle" font-size="14">5</text>
<rect x="125" y="40" width="35" height="35" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="142" y="62" fill="#fff" text-anchor="middle" font-size="14">2</text>
<rect x="170" y="40" width="35" height="35" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="187" y="62" fill="#fff" text-anchor="middle" font-size="14">4</text>
<rect x="215" y="40" width="35" height="35" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="232" y="62" fill="#fff" text-anchor="middle" font-size="14">3</text>
<rect x="260" y="40" width="35" height="35" fill="#4a4a4a" stroke="#888" stroke-width="2"/>
<text x="277" y="62" fill="#fff" text-anchor="middle" font-size="14">1</text>
</g>
<!-- Arrows down -->
<path d="M 170 85 L 170 110" stroke="#666" stroke-width="2" fill="none" marker-end="url(#arrowhead)"/>
<!-- Level 1: First split -->
<g id="level1">
<text x="20" y="135" fill="#888" font-size="12">Level 1:</text>
<rect x="60" y="120" width="35" height="35" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
<text x="77" y="142" fill="#fff" text-anchor="middle" font-size="14">5</text>
<rect x="105" y="120" width="35" height="35" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
<text x="122" y="142" fill="#fff" text-anchor="middle" font-size="14">2</text>
<rect x="150" y="120" width="35" height="35" fill="#ff6b6b" stroke="#ff6b6b" stroke-width="2"/>
<text x="167" y="142" fill="#fff" text-anchor="middle" font-size="14">4</text>
<rect x="230" y="120" width="35" height="35" fill="#4169e1" stroke="#4169e1" stroke-width="2"/>
<text x="247" y="142" fill="#fff" text-anchor="middle" font-size="14">3</text>
<rect x="275" y="120" width="35" height="35" fill="#4169e1" stroke="#4169e1" stroke-width="2"/>
<text x="292" y="142" fill="#fff" text-anchor="middle" font-size="14">1</text>
</g>
<!-- Arrows down -->
<path d="M 120 165 L 120 190" stroke="#666" stroke-width="2" fill="none"/>
<path d="M 260 165 L 260 190" stroke="#666" stroke-width="2" fill="none"/>
<!-- Level 2: Final split -->
<g id="level2">
<text x="20" y="215" fill="#888" font-size="12">Level 2:</text>
<rect x="60" y="200" width="35" height="35" fill="#ffa500" stroke="#ffa500" stroke-width="2"/>
<text x="77" y="222" fill="#fff" text-anchor="middle" font-size="14">5</text>
<rect x="105" y="200" width="35" height="35" fill="#ffa500" stroke="#ffa500" stroke-width="2"/>
<text x="122" y="222" fill="#fff" text-anchor="middle" font-size="14">2</text>
<rect x="150" y="200" width="35" height="35" fill="#ffa500" stroke="#ffa500" stroke-width="2"/>
<text x="167" y="222" fill="#fff" text-anchor="middle" font-size="14">4</text>
<rect x="230" y="200" width="35" height="35" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="247" y="222" fill="#fff" text-anchor="middle" font-size="14">3</text>
<rect x="275" y="200" width="35" height="35" fill="#51cf66" stroke="#51cf66" stroke-width="2"/>
<text x="292" y="222" fill="#fff" text-anchor="middle" font-size="14">1</text>
</g>
<!-- Merge Phase label -->
<text x="350" y="280" fill="#e0e0e0" font-size="16" text-anchor="middle" font-weight="bold">Merge Phase</text>
<!-- Merge step 1 -->
<text x="20" y="315" fill="#888" font-size="12">Merge 1:</text>
<rect x="80" y="300" width="35" height="35" fill="#9c27b0" stroke="#9c27b0" stroke-width="2"/>
<text x="97" y="322" fill="#fff" text-anchor="middle" font-size="14">2</text>
<rect x="125" y="300" width="35" height="35" fill="#9c27b0" stroke="#9c27b0" stroke-width="2"/>
<text x="142" y="322" fill="#fff" text-anchor="middle" font-size="14">5</text>
<rect x="170" y="300" width="35" height="35" fill="#9c27b0" stroke="#9c27b0" stroke-width="2"/>
<text x="187" y="322" fill="#fff" text-anchor="middle" font-size="14">4</text>
<rect x="230" y="300" width="35" height="35" fill="#00bcd4" stroke="#00bcd4" stroke-width="2"/>
<text x="247" y="322" fill="#fff" text-anchor="middle" font-size="14">1</text>
<rect x="275" y="300" width="35" height="35" fill="#00bcd4" stroke="#00bcd4" stroke-width="2"/>
<text x="292" y="322" fill="#fff" text-anchor="middle" font-size="14">3</text>
<!-- Merge step 2 -->
<text x="20" y="380" fill="#888" font-size="12">Merge 2:</text>
<rect x="80" y="365" width="35" height="35" fill="#2196f3" stroke="#2196f3" stroke-width="2"/>
<text x="97" y="387" fill="#fff" text-anchor="middle" font-size="14">1</text>
<rect x="125" y="365" width="35" height="35" fill="#2196f3" stroke="#2196f3" stroke-width="2"/>
<text x="142" y="387" fill="#fff" text-anchor="middle" font-size="14">2</text>
<rect x="170" y="365" width="35" height="35" fill="#2196f3" stroke="#2196f3" stroke-width="2"/>
<text x="187" y="387" fill="#fff" text-anchor="middle" font-size="14">3</text>
<rect x="215" y="365" width="35" height="35" fill="#2196f3" stroke="#2196f3" stroke-width="2"/>
<text x="232" y="387" fill="#fff" text-anchor="middle" font-size="14">4</text>
<rect x="260" y="365" width="35" height="35" fill="#2196f3" stroke="#2196f3" stroke-width="2"/>
<text x="277" y="387" fill="#fff" text-anchor="middle" font-size="14">5</text>
<!-- Arrow marker definition -->
<defs>
<marker id="arrowhead" markerWidth="10" markerHeight="10" refX="5" refY="5" orient="auto">
<polygon points="0 0, 10 5, 0 10" fill="#666"/>
</marker>
</defs>
</svg>
Why Merge Sort is Great
- Guaranteed O(n log n): Unlike quicksort, merge sort has consistent performance
- Stable sort: Maintains the relative order of equal elements
- Suitable for linked lists: Can sort linked lists efficiently with O(1) extra space
- Parallelizable: Can be split across multiple processors
The main tradeoff is that merge sort requires O(n) extra space, whereas insertion sort and bubble sort are O(1) space algorithms.
Quiz Time
Test your understanding of merge sort with these questions: