Merge Sort — VisualAlgorithms Docs

How it works

Merge Sort divides the array in half, recursively sorts each half, then merges the two sorted halves into one. The merge step walks both halves with two pointers, always copying the smaller front element next.

The recursion depth is log n and each level does O(n) work to merge, giving a guaranteed O(n log n) regardless of input order.

Implementation

      
 function mergeSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const mid = Math.floor((lo + hi) / 2);
  mergeSort(arr, lo, mid);
  mergeSort(arr, mid + 1, hi);
  const left = arr.slice(lo, mid+1);
  const right = arr.slice(mid+1, hi+1);
  let i = 0, j = 0, k = lo;
  while (i < left.length && j < right.length)
    arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
  while (i < left.length) arr[k++] = left[i++];
  while (j < right.length) arr[k++] = right[j++];
} def merge_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return
    mid = (lo + hi) // 2
    merge_sort(arr, lo, mid)
    merge_sort(arr, mid + 1, hi)
    left = arr[lo:mid+1]
    right = arr[mid+1:hi+1]
    i = j = 0; k = lo
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]; i += 1
        else:
            arr[k] = right[j]; j += 1
        k += 1 void mergeSort(vector<int>& arr, int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;
  mergeSort(arr, lo, mid);
  mergeSort(arr, mid+1, hi);
  vector<int> left(arr.begin()+lo, arr.begin()+mid+1);
  vector<int> right(arr.begin()+mid+1, arr.begin()+hi+1);
  int i=0, j=0, k=lo;
  while (i<left.size() && j<right.size())
    arr[k++] = left[i]<=right[j] ? left[i++] : right[j++];
  while (i<left.size()) arr[k++] = left[i++];
  while (j<right.size()) arr[k++] = right[j++];
} void MergeSort(int[] arr, int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo + hi) / 2;
  MergeSort(arr, lo, mid);
  MergeSort(arr, mid + 1, hi);
  int[] left = arr[lo..(mid+1)];
  int[] right = arr[(mid+1)..(hi+1)];
  int i = 0, j = 0, k = lo;
  while (i < left.Length && j < right.Length)
    arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
  while (i < left.Length) arr[k++] = left[i++];
  while (j < right.Length) arr[k++] = right[j++];
} void merge(int arr[], int lo, int mid, int hi) {
  int n1 = mid-lo+1, n2 = hi-mid;
  int L[n1], R[n2];
  for (int i=0;i<n1;i++) L[i]=arr[lo+i];
  for (int j=0;j<n2;j++) R[j]=arr[mid+1+j];
  int i=0,j=0,k=lo;
  while (i<n1 && j<n2)
    arr[k++] = L[i]<=R[j] ? L[i++] : R[j++];
  while (i<n1) arr[k++] = L[i++];
  while (j<n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int lo, int hi) {
  if (lo >= hi) return;
  int mid = (lo+hi)/2;
  mergeSort(arr,lo,mid);
  mergeSort(arr,mid+1,hi);
  merge(arr,lo,mid,hi);
} 

Advantages

Guaranteed O(n log n) on every input — no pathological cases.
Stable, which makes it the standard choice for sorting records by a secondary key.
Predictable and easy to parallelize or adapt to external (on-disk) sorting.

Disadvantages

Needs O(n) auxiliary memory for the classic implementation.
Not in-place, and slower than Quick Sort in practice on small in-memory arrays due to the extra copying.

When to use it

Reach for it when stability matters, when worst-case guarantees matter, or when sorting data larger than RAM via external merge passes.