Replacing the Linear Scan in Selection Sort

Traditional selection sort repeatedyl picks the smallest element from the unsorted suffix and swaps it forward. The bottleneck is the linear scan that finds that minimum, giving an overall Θ(n²) runtime.

static void naiveSelection(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minPos = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minPos]) minPos = j;
        }
        int tmp = a[i];
        a[i] = a[minPos];
        a[minPos] = tmp;
    }
}

Heap as an Indexing Accelerator

A max-heap can deliver the largest remaining key in Θ(log n) time. A direct adaptation, however, allocates a second array and copies every extracted maximum into it, then copies back—Θ(n log n) time but Θ(n) extra space.

static void heapCopySort(Integer[] src) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    Collections.addAll(pq, src);
    int[] tmp = new int[src.length];
    for (int i = src.length - 1; i >= 0; i--) {
        tmp[i] = pq.poll();
    }
    System.arraycopy(tmp, 0, src, 0, src.length);
}

In-Place Heap Sort

Heap sort eliminates the auxiliary array by treating the original array itself as the heap. After the initial heapify, the largest element is repeated swapped to the end of the shrinking heap and the heap property is restored via a sift-down.

Walk-through

1. Build a max-heap from the entire array in Θ(n) time. No extra storage is required.
2. For i from n-1 down to 1:
   • Swap a[0] (current maximum) with a[i].
   • Reduce the heap size by one.
   • Restore the heap property at the root with a sift-down on the prefix a[0..i-1].

Reference Implementation

public static void heapSort(int[] a) {
    int n = a.length;

    /* 1. bottom-up heapify */
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(a, i, n);
    }

    /* 2. extract max repeatedly */
    for (int end = n - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

private static void siftDown(int[] a, int root, int size) {
    int val = a[root];
    while (true) {
        int left  = 2 * root + 1;
        int right = left + 1;
        if (left >= size) break;

        int larger = left;
        if (right < size && a[right] > a[left]) larger = right;
        if (val >= a[larger]) break;

        a[root] = a[larger];
        root = larger;
    }
    a[root] = val;
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

Complexity: Θ(n log n) time, Θ(1) auxiliary space.