Partial Sort Selection

Partial Sort Selection finds the k-th smallest element by sorting only the first $k + 1$ smallest elements, rather than the entire array.

This method is simple and often practical when you also need the smallest $k$ elements in sorted order.

Problem

Given an array $A$ of length $n$ and an integer $k$ with $0 \le k < n$, return the k-th smallest element.

Algorithm

Rearrange the array so that the smallest $k + 1$ elements occupy the first part, and sort only that prefix.

partial_sort_selection(A, k):
    build max heap H from first k + 1 elements

    for i from k + 1 to n - 1:
        if A[i] < max(H):
            replace max(H) with A[i]

    sort H

    return H[k]

This produces the smallest $k + 1$ elements in sorted order.

Alternative Form

Using selection + sort:

partial_sort_selection(A, k):
    quickselect to partition around k
    sort A[0..k]
    return A[k]

Example

Let

$$ A = [7, 2, 9, 4, 3] $$

and

$$ k = 2 $$

The smallest three elements are:

$$ [2, 3, 4] $$

After sorting this prefix, the k-th element is:

$$ 4 $$

Correctness

After the heap phase, the structure contains the smallest $k + 1$ elements of the array. Sorting this subset produces the correct order. The element at index $k$ within this subset is the k-th smallest element globally.

Complexity

method	time
heap based	$O(n \log k + k \log k)$
selection + sort	$O(n + k \log k)$

Space:

$$ O(k) $$

When to Use

Use Partial Sort Selection when:

• you need both the k-th element and the smallest $k$ elements
• $k$ is much smaller than $n$
• sorted output for the prefix is required

If only the k-th element is needed, Quickselect is usually faster.

Implementation

import heapq

def partial_sort_selection(a, k):
    heap = [-x for x in a[:k+1]]
    heapq.heapify(heap)

    for x in a[k+1:]:
        if x < -heap[0]:
            heapq.heapreplace(heap, -x)

    result = sorted([-x for x in heap])
    return result[k]

func PartialSortSelection(a []int, k int) int {
	h := &MaxHeap{}
	heap.Init(h)

	for i := 0; i < k+1; i++ {
		heap.Push(h, a[i])
	}

	for i := k + 1; i < len(a); i++ {
		if a[i] < (*h)[0] {
			heap.Pop(h)
			heap.Push(h, a[i])
		}
	}

	tmp := make([]int, h.Len())
	copy(tmp, *h)
	sortInts(tmp)

	return tmp[k]
}