Sorting Algorithms Explained: Bubble, Selection, Insertion, and Merge Sort

Sorting is usually the first real algorithm most of us write, and it's a great way to build intuition for time complexity, in-place mutation, and divide-and-conquer thinking. This post walks through four classic algorithms — bubble sort, selection sort, insertion sort, and merge sort — with an animated visualization for each, plus Java and JavaScript implementations.

Each visualization is interactive: hit Play to watch it sort step by step, or Shuffle to try a different starting order.

Bubble Sort

Bubble sort repeatedly walks through the array, comparing adjacent elements and swapping them if they're in the wrong order. The largest unsorted element "bubbles up" to its correct position at the end of each pass.

• Time complexity: O(n²) average and worst case, O(n) best case (already sorted, with an early-exit check)
• Space complexity: O(1) — sorts in place
• Stable: yes

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

Selection Sort

Selection sort splits the array into a sorted prefix and an unsorted suffix. On each pass, it scans the unsorted portion to find the minimum element and swaps it into place at the front of that portion.

• Time complexity: O(n²) in all cases — it always scans the remaining unsorted elements, even if the array is already sorted
• Space complexity: O(1) — sorts in place
• Stable: no (the swap can move an equal element past another)

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

Insertion Sort

Insertion sort builds up a sorted prefix one element at a time — it takes the next unsorted element and shifts it backward into its correct position within the already-sorted portion. It's the algorithm most people use intuitively when sorting a hand of playing cards.

• Time complexity: O(n²) average and worst case, O(n) best case (nearly sorted input)
• Space complexity: O(1) — sorts in place
• Stable: yes
• Efficient for small or nearly-sorted datasets, which is why it's often used as the base case inside hybrid sorts like Timsort

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

Merge Sort

Merge sort is divide-and-conquer: split the array in half recursively until each piece has one element, then merge pairs of sorted pieces back together. Unlike the previous three, it doesn't sort in place — merging requires auxiliary storage.

• Time complexity: O(n log n) in all cases — the split/merge structure doesn't depend on the input's initial order
• Space complexity: O(n) — needs extra space for the merge step
• Stable: yes

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
    int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);
    int i = 0, j = 0, k = left;
    while (i < leftArr.length && j < rightArr.length) {
        arr[k++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.length) arr[k++] = leftArr[i++];
    while (j < rightArr.length) arr[k++] = rightArr[j++];
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

Comparison

Bubble, selection, and insertion sort are all O(n²) and mainly useful for learning or tiny inputs — insertion sort is the pick of the three for nearly-sorted data. Merge sort trades O(n) extra space for a guaranteed O(n log n) runtime, which is why it (or a hybrid like Timsort) shows up in real-world standard library sort implementations.