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, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  const INSERTION_THRESHOLD = 16;
  const aux = new Array(n);
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  metrics.insertionThreshold = INSERTION_THRESHOLD;
  function writeValue(index, value) {
    arr[index] = value;
    recordMetric('writeOperations');
    write(index, value);
  }
  function insertionSort(lo, hi) {
    recordMetric('insertionSortCalls');
    for (let i = lo + 1; i <= hi; i++) {
      const value = arr[i];
      let j = i;
      while (j > lo) {
        compare(j - 1, i);
        if (arr[j - 1] <= value) break;
        writeValue(j, arr[j - 1]);
        j--;
      }
      writeValue(j, value);
    }
  }
  function merge(lo, mid, hi) {
    for (let i = lo; i <= hi; i++) aux[i] = arr[i];
    compare(mid, mid + 1);
    if (aux[mid] <= aux[mid + 1]) {
      recordMetric('mergeSkips');
      return;
    }
    let left = lo;
    let right = mid + 1;
    let dest = lo;
    while (left <= mid && right <= hi) {
      compare(left, right);
      if (aux[left] <= aux[right]) writeValue(dest++, aux[left++]); else writeValue(dest++, aux[right++]);
    }
    while (left <= mid) writeValue(dest++, aux[left++]);
    while (right <= hi) writeValue(dest++, aux[right++]);
    recordMetric('mergeCalls');
    checkpoint(Math.min(metrics.mergeCalls, n), n);
  }
  function sort(lo, hi) {
    if (hi - lo + 1 <= INSERTION_THRESHOLD) {
      insertionSort(lo, hi);
      return;
    }
    const mid = lo + (hi - lo >> 1);
    sort(lo, mid);
    sort(mid + 1, hi);
    merge(lo, mid, hi);
  }
  sort(0, n - 1);
  for (let i = 0; i < n; i++) markSorted(i);
  checkpoint(n, n);
}
 def mergeSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def writeValue(index, value):
        arr[index] = value
        recordMetric("writeOperations")
        write(index, value)

    def insertionSort(lo, hi):
        recordMetric("insertionSortCalls")
        for i in range((lo + 1), (hi + 1)):
            value = arr[i]
            j = i
            while (j > lo):
                compare((j - 1), i)
                if (arr[(j - 1)] <= value):
                    break
                writeValue(j, arr[(j - 1)])
                j -= 1
            writeValue(j, value)

    def merge(lo, mid, hi):
        for i in range(lo, (hi + 1)):
            aux[i] = arr[i]
        compare(mid, (mid + 1))
        if (aux[mid] <= aux[(mid + 1)]):
            recordMetric("mergeSkips")
            return
        left = lo
        right = (mid + 1)
        dest = lo
        while ((left <= mid) and (right <= hi)):
            compare(left, right)
            if (aux[left] <= aux[right]):
                writeValue(((dest := dest + 1) - 1), aux[((left := left + 1) - 1)])
            else:
                writeValue(((dest := dest + 1) - 1), aux[((right := right + 1) - 1)])
        while (left <= mid):
            writeValue(((dest := dest + 1) - 1), aux[((left := left + 1) - 1)])
        while (right <= hi):
            writeValue(((dest := dest + 1) - 1), aux[((right := right + 1) - 1)])
        recordMetric("mergeCalls")
        checkpoint((metrics.mergeCalls if metrics.mergeCalls <= n else n), n)

    def sort(lo, hi):
        if (((hi - lo) + 1) <= INSERTION_THRESHOLD):
            insertionSort(lo, hi)
            return
        mid = (lo + ((hi - lo) >> 1))
        sort(lo, mid)
        sort((mid + 1), hi)
        merge(lo, mid, hi)

    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    INSERTION_THRESHOLD = 16
    aux = [0] * n
    metrics.insertionThreshold = INSERTION_THRESHOLD
    sort(0, (n - 1))
    for i in range(n):
        markSorted(i)
    checkpoint(n, n)
 #include <vector>
#include <algorithm>
void recordMetric(int name, int );
void writeValue(int index, int value);
void insertionSort(int lo, int hi);
void merge(int lo, int mid, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void writeValue(int index, int value) {
    arr[index] = value;
    recordMetric("writeOperations");
    write(index, value);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            writeValue(j, arr[(j - 1)]);
            j--;
        }
        writeValue(j, value);
    }
}

void merge(int lo, int mid, int hi) {
    for(int i=lo; i<(hi + 1); i++) {
        aux[i] = arr[i];
    }
    compare(mid, (mid + 1));
    if((aux[mid] <= aux[(mid + 1)])) {
        recordMetric("mergeSkips");
        return;
    }
    int left = lo;
    int right = (mid + 1);
    int dest = lo;
    while(((left <= mid) && (right <= hi))) {
        compare(left, right);
        if((aux[left] <= aux[right])) {
            writeValue(dest++, aux[left++]);
        } else {
            writeValue(dest++, aux[right++]);
        }
    }
    while((left <= mid)) {
        writeValue(dest++, aux[left++]);
    }
    while((right <= hi)) {
        writeValue(dest++, aux[right++]);
    }
    recordMetric("mergeCalls");
    checkpoint(((metrics.mergeCalls) < (n) ? (metrics.mergeCalls) : (n)), n);
}

void sort(int lo, int hi) {
    if((((hi - lo) + 1) <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + ((hi - lo) >> 1));
    sort(lo, mid);
    sort((mid + 1), hi);
    merge(lo, mid, hi);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 16;
    std::vector<int> aux(n, 0);
    int metrics = educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
    checkpoint(n, n);
} void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void writeValue(int index, int value) {
    arr[index] = value;
    recordMetric("writeOperations");
    write(index, value);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            writeValue(j, arr[(j - 1)]);
            j--;
        }
        writeValue(j, value);
    }
}

void merge(int lo, int mid, int hi) {
    for(int i=lo; i<(hi + 1); i++) {
        aux[i] = arr[i];
    }
    compare(mid, (mid + 1));
    if((aux[mid] <= aux[(mid + 1)])) {
        recordMetric("mergeSkips");
        return;
    }
    int left = lo;
    int right = (mid + 1);
    int dest = lo;
    while(((left <= mid) && (right <= hi))) {
        compare(left, right);
        if((aux[left] <= aux[right])) {
            writeValue(dest++, aux[left++]);
        } else {
            writeValue(dest++, aux[right++]);
        }
    }
    while((left <= mid)) {
        writeValue(dest++, aux[left++]);
    }
    while((right <= hi)) {
        writeValue(dest++, aux[right++]);
    }
    recordMetric("mergeCalls");
    checkpoint(Math.Min(metrics.mergeCalls, n), n);
}

void sort(int lo, int hi) {
    if((((hi - lo) + 1) <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + ((hi - lo) >> 1));
    sort(lo, mid);
    sort((mid + 1), hi);
    merge(lo, mid, hi);
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 16;
    int[] aux = new int[n];
    int metrics = stats.educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
    checkpoint(n, n);
} #include <stdio.h>
#include <stdlib.h>
void recordMetric(int name, int );
void writeValue(int index, int value);
void insertionSort(int lo, int hi);
void merge(int lo, int mid, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void writeValue(int index, int value) {
    arr[index] = value;
    recordMetric("writeOperations");
    write(index, value);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            writeValue(j, arr[(j - 1)]);
            j--;
        }
        writeValue(j, value);
    }
}

void merge(int lo, int mid, int hi) {
    for(int i=lo; i<(hi + 1); i++) {
        aux[i] = arr[i];
    }
    compare(mid, (mid + 1));
    if((aux[mid] <= aux[(mid + 1)])) {
        recordMetric("mergeSkips");
        return;
    }
    int left = lo;
    int right = (mid + 1);
    int dest = lo;
    while(((left <= mid) && (right <= hi))) {
        compare(left, right);
        if((aux[left] <= aux[right])) {
            writeValue(dest++, aux[left++]);
        } else {
            writeValue(dest++, aux[right++]);
        }
    }
    while((left <= mid)) {
        writeValue(dest++, aux[left++]);
    }
    while((right <= hi)) {
        writeValue(dest++, aux[right++]);
    }
    recordMetric("mergeCalls");
    checkpoint(((metrics.mergeCalls) < (n) ? (metrics.mergeCalls) : (n)), n);
}

void sort(int lo, int hi) {
    if((((hi - lo) + 1) <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + ((hi - lo) >> 1));
    sort(lo, mid);
    sort((mid + 1), hi);
    merge(lo, mid, hi);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 16;
    int* aux = (int*)malloc((n) * sizeof(int));
    int metrics = (*educational).metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
    checkpoint(n, n);
} 
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.