Sorting Basics

Sorting means ordering by a rule

To sort a collection means to arrange its elements so that every neighboring pair follows the chosen rule. For numbers, this is often ascending order, but the rule itself can be anything: descending order, string length, one of an object's fields, and so on.

int[] values = {8, 3, 6, 1};
Arrays.sort(values);

// 1, 3, 6, 8

If an algorithm sorts numbers in ascending order, then after it finishes, every valid i must satisfy values[i] <= values[i + 1]. That is a simple description of the result, but the ways to reach it can differ greatly.

What to compare in sorting algorithms

Now that Big O is already familiar, sorting algorithms can be compared by more than whether they “work.” Important characteristics usually include time complexity, extra memory, behavior on nearly sorted data, and whether the original array must be modified.

For example, one algorithm may take O(n²) time but use almost no extra memory, while another runs in O(n log n) time but creates an auxiliary array. There is no universally best option for every situation.

Comparisons and swaps

Most classic sorts for arbitrary values are built around two actions: compare elements and, when necessary, change their positions. The algorithms differ in which elements they compare and how they gradually bring the entire array into order.