Java sorting: insertion sort, merge sort, and comparators

The concept

Insertion sort grows a sorted prefix: it takes the next element and shifts larger elements to the right until it finds the right place. It is simple and fast for short or nearly sorted input but takes O(n²) in the worst case. Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves in linear time, giving O(n log n) always, at the cost of O(n) extra space.

In real programs use Arrays.sort or List.sort. For objects they use a stable merge-based sort (TimSort), which keeps equal elements in their original order. A Comparator describes the order, and Comparator.comparing builds one from a key. Here strings are sorted by length first and then alphabetically.

Code example

import java.util.*;

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

  static int[] mergeSort(int[] a) {
    if (a.length <= 1) {
      return a;
    }
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, a.length / 2));
    int[] right = mergeSort(Arrays.copyOfRange(a, a.length / 2, a.length));
    int[] merged = new int[a.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
      merged[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    }
    while (i < left.length) {
      merged[k++] = left[i++];
    }
    while (j < right.length) {
      merged[k++] = right[j++];
    }
    return merged;
  }

  public static void main(String[] args) {
    int[] data = {5, 2, 9, 1, 5, 6};
    int[] copy = data.clone();
    insertionSort(copy);
    System.out.println(Arrays.toString(copy));
    System.out.println(Arrays.toString(mergeSort(data)));

    List<String> words = new ArrayList<>(List.of("pear", "fig", "apple", "kiwi", "plum"));
    words.sort(Comparator.comparing(String::length).thenComparing(Comparator.naturalOrder()));
    System.out.println(words);
  }
}

[1, 2, 5, 5, 6, 9]
[1, 2, 5, 5, 6, 9]
[fig, kiwi, pear, plum, apple]

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

—

[1, 2, 5, 5, 6, 9]

[1, 2, 5, 5, 6, 9]
[1, 2, 5, 5, 6, 9]

[1, 2, 5, 5, 6, 9]
[1, 2, 5, 5, 6, 9]
[fig, kiwi, pear, plum, apple]

Behind the scenes

Cost and common mistakes

Insertion sort O(n²) worst case and O(n) best case. Merge sort O(n log n) time and O(n) space.

• Without the <= in the merge step, equal elements could swap order, and the sort would not be stable.
• The merge sort here allocates new arrays at every level. A production version reuses one buffer.
• Comparators must be consistent. Subtracting two ints in compare can overflow, so use Integer.compare.

Try it yourself

Which sort would you use for 10 nearly sorted items, and which for a million random items?

Further reading

• Dev.java: learn Java (external)
• Java SE 17 API documentation (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)