Skip to content

11.6   Merge sort

Merge sort is a divide-and-conquer sorting algorithm with the “division” and “merging” phases shown below.

  1. Division: recursively split the array at its midpoint, turning the problem of sorting a long array into problems of sorting shorter arrays.
  2. Merging: stop dividing when a subarray has length 1, then repeatedly merge two shorter sorted arrays into one longer sorted array until the process is complete.

The division and merging phases of merge sortThe division and merging phases of merge sort

Figure 11-10   The division and merging phases of merge sort

11.6.1   Algorithm steps

As shown below, the division phase works from the top down, recursively splitting each array into two subarrays at its midpoint.

  1. Calculate the midpoint mid, then recursively divide the left subarray, [left, mid], and the right subarray, [mid + 1, right].
  2. Repeat step 1. recursively until each subarray has length 1.

The merging phase works from the bottom up, combining the left and right subarrays into a sorted array. Merging begins with subarrays of length 1, so every subarray involved in this phase is already sorted.

Steps of merge sortSteps of merge sort

merge_sort_step2merge_sort_step2

merge_sort_step3merge_sort_step3

merge_sort_step4merge_sort_step4

merge_sort_step5merge_sort_step5

merge_sort_step6merge_sort_step6

merge_sort_step7merge_sort_step7

merge_sort_step8merge_sort_step8

merge_sort_step9merge_sort_step9

merge_sort_step10merge_sort_step10

Figure 11-11   Steps of merge sort

Merge sort follows the same recursive order as a postorder traversal of a binary tree.

  • Postorder traversal: recurse into the left subtree, then the right subtree, and finally process the root.
  • Merge sort: recurse into the left subarray, then the right subarray, and finally merge them.

The implementation follows. The interval to merge in nums is [left, right], while its corresponding interval in tmp is [0, right - left].

merge_sort.py
def merge(nums: list[int], left: int, mid: int, right: int):
    """Merge the left and right subarrays"""
    # The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    # Create a temporary array tmp to store the merged result
    tmp = [0] * (right - left + 1)
    # Initialize the starting indices of the left and right subarrays
    i, j, k = left, mid + 1, 0
    # While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1
        k += 1
    # Copy the remaining elements of the left and right subarrays into the temporary array
    while i <= mid:
        tmp[k] = nums[i]
        i += 1
        k += 1
    while j <= right:
        tmp[k] = nums[j]
        j += 1
        k += 1
    # Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for k in range(0, len(tmp)):
        nums[left + k] = tmp[k]

def merge_sort(nums: list[int], left: int, right: int):
    """Merge sort"""
    # Base case
    if left >= right:
        return  # Stop recursing when the subarray has at most one element
    # Divide phase
    mid = (left + right) // 2 # Calculate the midpoint
    merge_sort(nums, left, mid)  # Recurse on the left subarray
    merge_sort(nums, mid + 1, right)  # Recurse on the right subarray
    # Merge phase
    merge(nums, left, mid, right)
merge_sort.cpp
/* Merge the left and right subarrays */
void merge(vector<int> &nums, int left, int mid, int right) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    vector<int> tmp(right - left + 1);
    // Initialize the starting indices of the left and right subarrays
    int i = left, j = mid + 1, k = 0;
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (k = 0; k < tmp.size(); k++) {
        nums[left + k] = tmp[k];
    }
}

/* Merge sort */
void mergeSort(vector<int> &nums, int left, int right) {
    // Base case
    if (left >= right)
        return; // Stop recursing when the subarray has at most one element
    // Divide phase
    int mid = left + (right - left) / 2;    // Calculate the midpoint
    mergeSort(nums, left, mid);      // Recurse on the left subarray
    mergeSort(nums, mid + 1, right); // Recurse on the right subarray
    // Merge phase
    merge(nums, left, mid, right);
}
merge_sort.java
/* Merge the left and right subarrays */
void merge(int[] nums, int left, int mid, int right) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    int[] tmp = new int[right - left + 1];
    // Initialize the starting indices of the left and right subarrays
    int i = left, j = mid + 1, k = 0;
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* Merge sort */
void mergeSort(int[] nums, int left, int right) {
    // Base case
    if (left >= right)
        return; // Stop recursing when the subarray has at most one element
    // Divide phase
    int mid = left + (right - left) / 2; // Calculate the midpoint
    mergeSort(nums, left, mid); // Recurse on the left subarray
    mergeSort(nums, mid + 1, right); // Recurse on the right subarray
    // Merge phase
    merge(nums, left, mid, right);
}
merge_sort.cs
/* Merge the left and right subarrays */
void Merge(int[] nums, int left, int mid, int right) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    int[] tmp = new int[right - left + 1];
    // Initialize the starting indices of the left and right subarrays
    int i = left, j = mid + 1, k = 0;
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (k = 0; k < tmp.Length; ++k) {
        nums[left + k] = tmp[k];
    }
}

/* Merge sort */
void MergeSort(int[] nums, int left, int right) {
    // Base case
    if (left >= right) return;       // Stop recursing when the subarray has at most one element
    // Divide phase
    int mid = left + (right - left) / 2;    // Calculate the midpoint
    MergeSort(nums, left, mid);      // Recurse on the left subarray
    MergeSort(nums, mid + 1, right); // Recurse on the right subarray
    // Merge phase
    Merge(nums, left, mid, right);
}
merge_sort.go
/* Merge the left and right subarrays */
func merge(nums []int, left, mid, right int) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    tmp := make([]int, right-left+1)
    // Initialize the starting indices of the left and right subarrays
    i, j, k := left, mid+1, 0
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    for i <= mid && j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[i]
            i++
        } else {
            tmp[k] = nums[j]
            j++
        }
        k++
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    for i <= mid {
        tmp[k] = nums[i]
        i++
        k++
    }
    for j <= right {
        tmp[k] = nums[j]
        j++
        k++
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for k := 0; k < len(tmp); k++ {
        nums[left+k] = tmp[k]
    }
}

/* Merge sort */
func mergeSort(nums []int, left, right int) {
    // Base case
    if left >= right {
        return
    }
    // Divide phase
    mid := left + (right - left) / 2
    mergeSort(nums, left, mid)
    mergeSort(nums, mid+1, right)
    // Merge phase
    merge(nums, left, mid, right)
}
merge_sort.swift
/* Merge the left and right subarrays */
func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    var tmp = Array(repeating: 0, count: right - left + 1)
    // Initialize the starting indices of the left and right subarrays
    var i = left, j = mid + 1, k = 0
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while i <= mid, j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[i]
            i += 1
        } else {
            tmp[k] = nums[j]
            j += 1
        }
        k += 1
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while i <= mid {
        tmp[k] = nums[i]
        i += 1
        k += 1
    }
    while j <= right {
        tmp[k] = nums[j]
        j += 1
        k += 1
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for k in tmp.indices {
        nums[left + k] = tmp[k]
    }
}

/* Merge sort */
func mergeSort(nums: inout [Int], left: Int, right: Int) {
    // Base case
    if left >= right { // Stop recursing when the subarray has at most one element
        return
    }
    // Divide phase
    let mid = left + (right - left) / 2 // Calculate the midpoint
    mergeSort(nums: &nums, left: left, right: mid) // Recurse on the left subarray
    mergeSort(nums: &nums, left: mid + 1, right: right) // Recurse on the right subarray
    // Merge phase
    merge(nums: &nums, left: left, mid: mid, right: right)
}
merge_sort.js
/* Merge the left and right subarrays */
function merge(nums, left, mid, right) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    const tmp = new Array(right - left + 1);
    // Initialize the starting indices of the left and right subarrays
    let i = left,
        j = mid + 1,
        k = 0;
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* Merge sort */
function mergeSort(nums, left, right) {
    // Base case
    if (left >= right) return; // Stop recursing when the subarray has at most one element
    // Divide phase
    let mid = Math.floor(left + (right - left) / 2); // Calculate the midpoint
    mergeSort(nums, left, mid); // Recurse on the left subarray
    mergeSort(nums, mid + 1, right); // Recurse on the right subarray
    // Merge phase
    merge(nums, left, mid, right);
}
merge_sort.ts
/* Merge the left and right subarrays */
function merge(nums: number[], left: number, mid: number, right: number): void {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    const tmp = new Array(right - left + 1);
    // Initialize the starting indices of the left and right subarrays
    let i = left,
        j = mid + 1,
        k = 0;
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
    }
}

/* Merge sort */
function mergeSort(nums: number[], left: number, right: number): void {
    // Base case
    if (left >= right) return; // Stop recursing when the subarray has zero or one element
    // Divide phase
    let mid = Math.floor(left + (right - left) / 2); // Calculate the midpoint
    mergeSort(nums, left, mid); // Recurse on the left subarray
    mergeSort(nums, mid + 1, right); // Recurse on the right subarray
    // Merge phase
    merge(nums, left, mid, right);
}
merge_sort.dart
/* Merge the left and right subarrays */
void merge(List<int> nums, int left, int mid, int right) {
  // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
  // Create a temporary array tmp to store the merged result
  List<int> tmp = List.filled(right - left + 1, 0);
  // Initialize the starting indices of the left and right subarrays
  int i = left, j = mid + 1, k = 0;
  // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
  while (i <= mid && j <= right) {
    if (nums[i] <= nums[j])
      tmp[k++] = nums[i++];
    else
      tmp[k++] = nums[j++];
  }
  // Copy the remaining elements of the left and right subarrays into the temporary array
  while (i <= mid) {
    tmp[k++] = nums[i++];
  }
  while (j <= right) {
    tmp[k++] = nums[j++];
  }
  // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
  for (k = 0; k < tmp.length; k++) {
    nums[left + k] = tmp[k];
  }
}

/* Merge sort */
void mergeSort(List<int> nums, int left, int right) {
  // Base case
  if (left >= right) return; // Stop recursing when the subarray has at most one element
  // Divide phase
  int mid = left + (right - left) ~/ 2; // Calculate the midpoint
  mergeSort(nums, left, mid); // Recurse on the left subarray
  mergeSort(nums, mid + 1, right); // Recurse on the right subarray
  // Merge phase
  merge(nums, left, mid, right);
}
merge_sort.rs
/* Merge the left and right subarrays */
fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    let tmp_size = right - left + 1;
    let mut tmp = vec![0; tmp_size];
    // Initialize the starting indices of the left and right subarrays
    let (mut i, mut j, mut k) = (left, mid + 1, 0);
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while i <= mid && j <= right {
        if nums[i] <= nums[j] {
            tmp[k] = nums[i];
            i += 1;
        } else {
            tmp[k] = nums[j];
            j += 1;
        }
        k += 1;
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while i <= mid {
        tmp[k] = nums[i];
        k += 1;
        i += 1;
    }
    while j <= right {
        tmp[k] = nums[j];
        k += 1;
        j += 1;
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for k in 0..tmp_size {
        nums[left + k] = tmp[k];
    }
}

/* Merge sort */
fn merge_sort(nums: &mut [i32], left: usize, right: usize) {
    // Base case
    if left >= right {
        return; // Stop recursing when the subarray has at most one element
    }

    // Divide phase
    let mid = left + (right - left) / 2; // Calculate the midpoint
    merge_sort(nums, left, mid); // Recurse on the left subarray
    merge_sort(nums, mid + 1, right); // Recurse on the right subarray

    // Merge phase
    merge(nums, left, mid, right);
}
merge_sort.c
/* Merge the left and right subarrays */
void merge(int *nums, int left, int mid, int right) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    int tmpSize = right - left + 1;
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    // Initialize the starting indices of the left and right subarrays
    int i = left, j = mid + 1, k = 0;
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (k = 0; k < tmpSize; ++k) {
        nums[left + k] = tmp[k];
    }
    // Free memory
    free(tmp);
}

/* Merge sort */
void mergeSort(int *nums, int left, int right) {
    // Base case
    if (left >= right)
        return; // Stop recursing when the subarray has at most one element
    // Divide phase
    int mid = left + (right - left) / 2;    // Calculate the midpoint
    mergeSort(nums, left, mid);      // Recurse on the left subarray
    mergeSort(nums, mid + 1, right); // Recurse on the right subarray
    // Merge phase
    merge(nums, left, mid, right);
}
merge_sort.kt
/* Merge the left and right subarrays */
fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
    // The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
    // Create a temporary array tmp to store the merged result
    val tmp = IntArray(right - left + 1)
    // Initialize the starting indices of the left and right subarrays
    var i = left
    var j = mid + 1
    var k = 0
    // While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++]
        else
            tmp[k++] = nums[j++]
    }
    // Copy the remaining elements of the left and right subarrays into the temporary array
    while (i <= mid) {
        tmp[k++] = nums[i++]
    }
    while (j <= right) {
        tmp[k++] = nums[j++]
    }
    // Copy the elements of temporary array tmp back into the corresponding range of the original array nums
    for (l in tmp.indices) {
        nums[left + l] = tmp[l]
    }
}

/* Merge sort */
fun mergeSort(nums: IntArray, left: Int, right: Int) {
    // Base case
    if (left >= right) return  // Stop recursing when the subarray has at most one element
    // Divide phase
    val mid = left + (right - left) / 2 // Calculate the midpoint
    mergeSort(nums, left, mid) // Recurse on the left subarray
    mergeSort(nums, mid + 1, right) // Recurse on the right subarray
    // Merge phase
    merge(nums, left, mid, right)
}
merge_sort.rb
### Merge the left and right subarrays ###
def merge(nums, left, mid, right)
  # The left subarray spans [left, mid], and the right subarray spans [mid+1, right]
  # Create a temporary array tmp to store the merged result
  tmp = Array.new(right - left + 1, 0)
  # Initialize the starting indices of the left and right subarrays
  i, j, k = left, mid + 1, 0
  # While both subarrays have elements remaining, compare them and copy the smaller element into the temporary array
  while i <= mid && j <= right
    if nums[i] <= nums[j]
      tmp[k] = nums[i]
      i += 1
    else
      tmp[k] = nums[j]
      j += 1
    end
    k += 1
  end
  # Copy the remaining elements of the left and right subarrays into the temporary array
  while i <= mid
    tmp[k] = nums[i]
    i += 1
    k += 1
  end
  while j <= right
    tmp[k] = nums[j]
    j += 1
    k += 1
  end
  # Copy the elements of temporary array tmp back into the corresponding range of the original array nums
  (0...tmp.length).each do |k|
    nums[left + k] = tmp[k]
  end
end

### Merge sort ###
def merge_sort(nums, left, right)
  # Base case
  # Stop recursing when the subarray contains at most one element
  return if left >= right
  # Divide phase
  mid = left + (right - left) / 2 # Calculate the midpoint
  merge_sort(nums, left, mid) # Recurse on the left subarray
  merge_sort(nums, mid + 1, right) # Recurse on the right subarray
  # Merge phase
  merge(nums, left, mid, right)
end
Visualize execution

11.6.2   Algorithm properties

  • Time complexity: \(O(n \log n)\); not adaptive. Division produces a recursion tree of height \(\log n\). Merging performs a total of \(n\) operations at each level, giving \(O(n \log n)\) overall.
  • Space complexity: \(O(n)\); not in-place. The recursion depth is \(\log n\), requiring \(O(\log n)\) space for stack frames. Merging uses an auxiliary array requiring \(O(n)\) extra space.
  • Stable. Merging preserves the order of equal elements.

11.6.3   Sorting linked lists

Merge sort has a significant advantage over other sorting algorithms for linked lists: it can reduce the space complexity of sorting a linked list to \(O(1)\).

  • Division: use iteration instead of recursion to divide the list, eliminating the space needed for recursive stack frames.
  • Merging: inserting and deleting linked-list nodes requires only changing references or pointers. Merging two short sorted lists into a longer one therefore needs no additional list.

The implementation is fairly involved. Interested readers can consult further resources for details.

Share your insights, questions, or suggestions in the comments