SimuVedaAlgorithms Lab Open in the lab

Sorting / Intermediate

Merge Sort Visualizer

Split the array in half until each piece has one value, then merge the pieces back together in order.

Start the Merge Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n log n)
Average timeO(n log n)
Worst timeO(n log n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Merge sort on 5 values. [5, 1, 4, 2, 8]
  2. Split [0..4] at the middle, index 2.
  3. Split [0..2] at the middle, index 1.
  4. Split [0..1] at the middle, index 0.
  5. [0..0] has one value, so it is already sorted.
  6. [1..1] has one value, so it is already sorted.
  7. Merge the sorted halves [0..0] and [1..1].
  8. Compare 5 from the left half with 1 from the right half.
  9. 1 is smaller. Take it from the right half. [1, 5, 4, 2, 8]
  10. One half is used up. The rest is already in order.
  11. [2..2] has one value, so it is already sorted.
  12. Merge the sorted halves [0..1] and [2..2].
  13. Compare 1 from the left half with 4 from the right half.
  14. 1 is smaller or equal. Take it.
  15. Compare 5 from the left half with 4 from the right half.
  16. 4 is smaller. Take it from the right half. [1, 4, 5, 2, 8]
  17. One half is used up. The rest is already in order.
  18. Split [3..4] at the middle, index 3.
  19. [3..3] has one value, so it is already sorted.
  20. [4..4] has one value, so it is already sorted.
  21. … 11 more steps …
  22. Compare 5 from the left half with 8 from the right half.
  23. 5 is smaller or equal. Take it.
  24. One half is used up. The rest is already in order.
  25. Sorted. 8 comparisons and 8 writes.

Try it with your own input →

Merge sort in Java, Python, C++, C and JavaScript

void mergeSort(int[] a, int l, int r) {
  if (l >= r) return;
  int m = (l + r) / 2;
  mergeSort(a, l, m);
  mergeSort(a, m + 1, r);
  merge(a, l, m, r);
}
void merge(int[] a, int l, int m, int r) {
  int[] L = copyOfRange(a, l, m + 1);
  int[] R = copyOfRange(a, m + 1, r + 1);
  int i = 0, j = 0, k = l;
  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) a[k++] = L[i++];
    else a[k++] = R[j++];
  }
  while (i < L.length) a[k++] = L[i++];
  while (j < R.length) a[k++] = R[j++];
}
def merge_sort(a, l, r):
    if l >= r:
        return
    m = (l + r) // 2
    merge_sort(a, l, m)
    merge_sort(a, m + 1, r)
    merge(a, l, m, r)

def merge(a, l, m, r):
    L = a[l:m + 1]
    R = a[m + 1:r + 1]
    i = j = 0; k = l
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            a[k] = L[i]; i += 1
        else:
            a[k] = R[j]; j += 1
        k += 1
    while i < len(L):
        a[k] = L[i]; i += 1; k += 1
    while j < len(R):
        a[k] = R[j]; j += 1; k += 1
void merge(vector<int>& a, int l, int m, int r);

void mergeSort(vector<int>& a, int l, int r) {
  if (l >= r) return;
  int m = (l + r) / 2;
  mergeSort(a, l, m);
  mergeSort(a, m + 1, r);
  merge(a, l, m, r);
}
void merge(vector<int>& a, int l, int m, int r) {
  vector<int> L(a.begin() + l, a.begin() + m + 1);
  vector<int> R(a.begin() + m + 1, a.begin() + r + 1);
  int i = 0, j = 0, k = l;
  while (i < (int)L.size() && j < (int)R.size()) {
    if (L[i] <= R[j]) a[k++] = L[i++];
    else a[k++] = R[j++];
  }
  while (i < (int)L.size()) a[k++] = L[i++];
  while (j < (int)R.size()) a[k++] = R[j++];
}
#include <stdlib.h>

void merge(int a[], int l, int m, int r);

void mergeSort(int a[], int l, int r) {
  if (l >= r) return;
  int m = (l + r) / 2;
  mergeSort(a, l, m);
  mergeSort(a, m + 1, r);
  merge(a, l, m, r);
}
void merge(int a[], int l, int m, int r) {
  int nl = m - l + 1, nr = r - m;
  int *L = malloc(nl * sizeof(int)), *R = malloc(nr * sizeof(int));
  for (int x = 0; x < nl; x++) L[x] = a[l + x];
  for (int x = 0; x < nr; x++) R[x] = a[m + 1 + x];
  int i = 0, j = 0, k = l;
  while (i < nl && j < nr) {
    if (L[i] <= R[j]) a[k++] = L[i++];
    else a[k++] = R[j++];
  }
  while (i < nl) a[k++] = L[i++];
  while (j < nr) a[k++] = R[j++];
  free(L); free(R);
}
function mergeSort(a, l, r) {
  if (l >= r) return;
  const m = Math.floor((l + r) / 2);
  mergeSort(a, l, m);
  mergeSort(a, m + 1, r);
  merge(a, l, m, r);
}
function merge(a, l, m, r) {
  const L = a.slice(l, m + 1);
  const R = a.slice(m + 1, r + 1);
  let i = 0, j = 0, k = l;
  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) a[k++] = L[i++];
    else a[k++] = R[j++];
  }
  while (i < L.length) a[k++] = L[i++];
  while (j < R.length) a[k++] = R[j++];
}

In an interview

The merge step is the core of "count inversions" and "merge k sorted lists". It is stable and always O(n log n).

More sorting