Java sorting: insertion sort, merge sort, and comparators
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.
Java
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);
}
}