Java sorting: insertion sort, merge sort, and comparators

Implement two sorts by hand and sort objects with a Comparator.

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]

Explanation

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.

—

—

—

[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]

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)