Sorting algorithms

Sorting puts items in order.

🔎 Unravel this example Prerequisites (2)

Learn these first

Arrays and the Arrays utilities Time complexity (Big O)

At a glance

Mental model

Sorting a hand of cards: insertion sort takes each new card and slides it into place; merge sort splits the pile in two, sorts each half, and merges them by always taking the smaller top card.

What happens, in order

1Bubble sort: repeatedly compare neighbours and swap if out of order (the largest "bubbles" to the end)Selection sort: find the smallest, put it first, repeat. Insertion sort: grow a sorted prefix by inserting the next element; fast on nearly sorted data.
2Merge sort: split in half, sort each half recursively, merge two sorted halves with two pointersAlways O(n log n), stable, uses O(n) extra space.
3Quicksort: choose a pivot, partition the data into smaller and larger than the pivot, recurse on both sidesAverage O(n log n), worst case O(n²) with bad pivots, sorts in place.
4Swapping two elements: int t = a[i]; a[i] = a[j]; a[j] = t;

Remember

Stable means equal elements keep their original order (important when sorting by one column after another)
You will rarely write your own: use Arrays.sort(a), list.sort(comparator), stream.sorted()
TimSort finds existing sorted runs in the data and merges them, so already sorted or reverse-sorted input is sorted in nearly linear time

Watch out

Writing your own sort instead of the library oneQuicksort with a poor pivot on sorted inputComparator that is inconsistentForgetting that Arrays.sort sorts in place

Example (highlighted lines explain it)

public class Sorts {  static void bubbleSort(int[] a) {    for (int i = 0; i < a.length - 1; i++)      for (int j = 0; j < a.length - 1 - i; j++)        if (a[j] > a[j + 1]) swap(a, j, j + 1);  }  static void quickSort(int[] a, int lo, int hi) {    if (lo >= hi) return;    int pivot = a[hi], i = lo;    for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(a, i++, j);    swap(a, i, hi);    quickSort(a, lo, i - 1);    quickSort(a, i + 1, hi);  }  static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }}

Read the full explanation (about 2 min)

Sorting puts items in order. Simple sorts (bubble, selection, insertion) are O(n²) and good for learning; merge sort and quicksort are O(n log n) and what real libraries use. In practice call Arrays.sort or list.sort.

A mental model

Sorting a hand of cards: insertion sort takes each new card and slides it into place; merge sort splits the pile in two, sorts each half, and merges them by always taking the smaller top card.

How it works

Bubble sort: repeatedly compare neighbours and swap if out of order (the largest "bubbles" to the end). Selection sort: find the smallest, put it first, repeat. Insertion sort: grow a sorted prefix by inserting the next element; fast on nearly sorted data.

Merge sort: split in half, sort each half recursively, merge two sorted halves with two pointers. Always O(n log n), stable, uses O(n) extra space.

Quicksort: choose a pivot, partition the data into smaller and larger than the pivot, recurse on both sides. Average O(n log n), worst case O(n²) with bad pivots, sorts in place.

Swapping two elements: int t = a[i]; a[i] = a[j]; a[j] = t;.

Going deeper

Stable means equal elements keep their original order (important when sorting by one column after another). Java uses TimSort for objects (stable merge/insertion hybrid) and dual-pivot quicksort for primitives.

You will rarely write your own: use Arrays.sort(a), list.sort(comparator), stream.sorted(). Know the algorithms for interviews and to reason about cost, for example why sort on a million items is fine but bubble sort is not.

To only get the k smallest or largest items, a PriorityQueue of size k is cheaper than sorting everything.

Under the hood

TimSort finds existing sorted runs in the data and merges them, so already sorted or reverse-sorted input is sorted in nearly linear time. Primitive arrays use a dual-pivot quicksort that is not stable (which does not matter for numbers).

Common mistakes

Writing your own sort instead of the library one.
Quicksort with a poor pivot on sorted input.
Comparator that is inconsistent.
Forgetting that Arrays.sort sorts in place.

How Unravel recognises it

When you paste code, Unravel looks for these signs of sorting algorithms. Spotting them yourself is a good habit when you read unfamiliar code:

Method names you declare: bubbleSort() quickSort() mergeSort() insertionSort() selectionSort() heapSort() partition() swap() merge() sort()

Part of a learning path

Algorithms and data structures · previous: Binary search · next: Two pointers and sliding window

Related concepts

Comparable and ComparatorJava language Time complexity (Big O)Java language RecursionJava language

Frequently asked questions

What is Sorting algorithms?

What are the most common mistakes with Sorting algorithms?

Writing your own sort instead of the library one. Quicksort with a poor pivot on sorted input. Comparator that is inconsistent. Forgetting that Arrays.sort sorts in place.

How can I see Sorting algorithms in real code?

Paste your own Java into Unravel and it will point out where sorting algorithms appears, explain how it works at the detail level you choose, and draw the flow of the code around it.