Sorting

Solution and explanation

What it is

Sorting arranges elements in a defined order (ascending, descending or by a key such as salary or date). Sorted data makes searching (binary search), de-duplication, grouping and merging much faster.

Comparing sorting algorithms

• Time complexity (best, average, worst).
• Space: in-place (O(1) extra) or not.
• Stability: a stable sort keeps equal elements in their original order (important when sorting records by a second key).
• Adaptivity: does it run faster on nearly sorted data?

Summary table

• Bubble sort: O(n²) average/worst, O(n) best (with early exit), O(1) space, stable.
• Selection sort: O(n²) always, O(1) space, not stable, minimum number of swaps.
• Insertion sort: O(n²) worst, O(n) best on nearly sorted data, O(1) space, stable.
• Merge sort: O(n log n) always, O(n) space, stable.
• Quick sort: O(n log n) average, O(n²) worst, O(log n) stack space, not stable.
• Heap sort: O(n log n) always, O(1) space, not stable.
• Counting/radix sort: O(n + k) for small integer ranges, not comparison based.

What Java uses

• Arrays.sort on primitives: dual-pivot quicksort.
• Arrays.sort on objects and Collections.sort: TimSort (merge + insertion sort), stable, O(n log n), very fast on partly sorted data.

int[] scores = {72, 15, 90, 41};
Arrays.sort(scores);                                   // [15, 41, 72, 90]

List<Employee> staff = new ArrayList<>(...);
staff.sort(Comparator.comparing(Employee::department)
                     .thenComparing(Employee::salary, Comparator.reverseOrder()));

Lower bound

Any comparison-based sort needs Ω(n log n) comparisons in the worst case, so merge, heap and quick sort are optimal in that model.

Note: in interviews, state stability and space alongside time complexity when you choose a sort.

Solution and explanation

Idea

Repeatedly compare adjacent elements and swap them if they are in the wrong order. After each pass, the largest remaining element "bubbles" to the end.

Pass 1 on [5, 1, 4, 2, 8]:
(5,1) swap → [1,5,4,2,8]
(5,4) swap → [1,4,5,2,8]
(5,2) swap → [1,4,2,5,8]
(5,8) ok   → 8 is in its final place

static void bubbleSort(int[] a) {
    for (int pass = 0; pass < a.length - 1; pass++) {
        boolean swapped = false;
        for (int i = 0; i < a.length - 1 - pass; i++) {
            if (a[i] > a[i + 1]) {
                int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;        // already sorted → stop early
    }
}

Complexity

• Worst/average O(n²), best O(n) with the swapped flag, O(1) space, stable.

Note: used for teaching; real code uses library sorts.

Solution and explanation

Idea

Divide the array into a sorted prefix and an unsorted suffix. Repeatedly select the minimum of the unsorted part and swap it to the end of the sorted part.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

Dry run on [64, 25, 12, 22, 11]

• i=0: min 11 → [11, 25, 12, 22, 64]
• i=1: min 12 → [11, 12, 25, 22, 64]
• i=2: min 22 → [11, 12, 22, 25, 64]
• i=3: already in place.

Complexity

• O(n²) comparisons in every case, O(1) space, at most n−1 swaps.
• Not stable (a swap can jump an equal element over another).

Note: useful when writes are expensive (e.g. flash memory), because it performs the fewest swaps.

Solution and explanation

Idea

Build the sorted array one element at a time, like sorting playing cards in your hand: take the next element and shift larger elements right until its correct position is found.

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

Dry run on [12, 11, 13, 5, 6]

• 11 → [11, 12, 13, 5, 6]
• 13 → no shift
• 5 → [5, 11, 12, 13, 6]
• 6 → [5, 6, 11, 12, 13]

Complexity

• Worst/average O(n²), best O(n) for already sorted input, O(1) space, stable, adaptive.

Note: excellent for small or nearly sorted arrays; TimSort uses insertion sort for short runs.

Solution and explanation

Idea (divide and conquer)

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into one sorted array.

[38, 27, 43, 3, 9, 82, 10]
split → [38, 27, 43, 3] [9, 82, 10]
       → [38, 27] [43, 3] [9, 82] [10]
sort+merge → [27, 38] [3, 43] [9, 82] [10]
           → [3, 27, 38, 43] [9, 10, 82]
           → [3, 9, 10, 27, 38, 43, 82]

static void mergeSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}
static void merge(int[] a, int lo, int mid, int hi) {
    int[] tmp = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= keeps it stable
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, lo, tmp.length);
}

Complexity

• Time O(n log n) in all cases: log n levels, O(n) merge work per level.
• Space O(n) for the temporary arrays. Stable.

Uses

Sorting linked lists (no random access needed), external sorting of files too big for memory, counting inversions.

Solution and explanation

Idea

Pick a pivot, partition the array so smaller elements go left and larger go right, then recursively sort both sides. The pivot ends up in its final position.

static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}
// Lomuto partition with the last element as pivot
static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) { swap(a, i, j); i++; }
    }
    swap(a, i, hi);
    return i;
}
static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

Dry run of one partition on [10, 80, 30, 90, 40, 50, 70], pivot 70

Elements < 70 move left: 10, 30, 40, 50 → pivot placed at index 4 → [10, 30, 40, 50, 70, 90, 80].

Complexity

• Average O(n log n); worst O(n²) when the pivot is always the smallest/largest (e.g. sorted input with a last-element pivot).
• Space O(log n) recursion on average. In place, not stable.

Avoiding the worst case

Random pivot, median-of-three pivot, or recursing into the smaller side first (limits stack depth to O(log n)).

Note: quicksort is usually fastest in practice because of good cache behaviour, which is why Java uses a quicksort variant for primitives.

Solution and explanation

Idea

1. Build a max-heap from the array (O(n)).
2. Repeatedly swap the root (largest) with the last element of the heap, shrink the heap by one and sift the new root down.

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);    // build max-heap
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;               // move max to the end
        heapify(a, end, 0);
    }
}
static void heapify(int[] a, int size, int i) {
    while (true) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < size && a[l] > a[largest]) largest = l;
        if (r < size && a[r] > a[largest]) largest = r;
        if (largest == i) return;
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        i = largest;
    }
}

Complexity

• Time O(n log n) in all cases; space O(1) (in place); not stable.

Note: guarantees O(n log n) without extra memory, which is why it is the fallback in introsort when quicksort recursion gets too deep.

Solution and explanation

Problem

Sort an array containing only 0, 1 and 2 in a single pass without a library sort (Dutch National Flag problem).

[2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2]

Approach 1: counting

Count zeros, ones and twos, then overwrite the array. Two passes, O(n) time, O(1) space.

Approach 2: three pointers (one pass, optimal)

• low: next position for 0; mid: current element; high: next position for 2.
• a[mid] == 0 → swap with low, low++, mid++.
• a[mid] == 1 → mid++.
• a[mid] == 2 → swap with high, high-- (do not advance mid; the swapped-in value is unchecked).

static void sortColors(int[] a) {
    int low = 0, mid = 0, high = a.length - 1;
    while (mid <= high) {
        if (a[mid] == 0)      swap(a, low++, mid++);
        else if (a[mid] == 1) mid++;
        else                  swap(a, mid, high--);
    }
}

Dry run on [2, 0, 1]

• mid 0 is 2 → swap with high → [1, 0, 2], high 1
• mid 0 is 1 → mid 1
• mid 1 is 0 → swap with low → [0, 1, 2]

Complexity

• Counting: O(n), two passes. Dutch flag: O(n), one pass, O(1) space.

Solution and explanation

Problem

An inversion is a pair (i, j) with i < j and a[i] > a[j]. Count them; it measures how far the array is from sorted.

[8, 4, 2, 1] → 6 inversions
[3, 1, 2]    → 2 ( (3,1) and (3,2) )

Approach 1: check every pair

Two nested loops. O(n²).

Approach 2: merge sort (optimal)

While merging two sorted halves, when an element from the right half is placed before remaining elements of the left half, it forms an inversion with each of them: add (mid − i + 1).

static long countInversions(int[] a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = countInversions(a, lo, mid) + countInversions(a, mid + 1, hi);
    int[] tmp = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else { tmp[k++] = a[j++]; count += mid - i + 1; }   // a[i..mid] all greater than a[j]
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, lo, tmp.length);
    return count;
}

Complexity

• Brute force O(n²). Merge sort O(n log n) time, O(n) space. A Fenwick tree also gives O(n log n).

Real-world use

Ranking similarity (how differently two people ordered the same list) in recommendation systems.