Partial Sort

Partial sort places the smallest ( k ) elements of a sequence into sorted order at the front, while leaving the remaining elements unordered. It avoids the cost of a full sort when only a prefix of sorted data is needed.

You use it when you care about top ( k ) elements rather than the entire ordering.

Problem

Given an array ( A ) of length ( n ) and an integer ( k ), rearrange ( A ) such that:

• The first ( k ) elements are the smallest ( k ) values in sorted order
• The remaining ( n - k ) elements may appear in any order

Algorithm (Heap based)

Maintain a max heap of size ( k ). This heap stores the current smallest ( k ) elements.

1. Insert first ( k ) elements into a max heap

2. For each remaining element:

   • If it is smaller than the heap maximum, replace the maximum

3. Extract elements from heap and sort them

partial_sort(A, k):
    heap = max_heap()

    for i in 0..k-1:
        heap.push(A[i])

    for i in k..n-1:
        if A[i] < heap.top():
            heap.pop()
            heap.push(A[i])

    result = []
    while heap not empty:
        result.append(heap.pop())

    reverse(result)
    return result

Example

Let:

( A = [9, 1, 7, 3, 2, 8, 5] ), ( k = 3 )

Smallest 3 elements:

( [1, 2, 3] )

Final arrangement (one valid result):

( [1, 2, 3, \dots] )

Remaining elements can be in any order.

Correctness

The heap always contains the smallest ( k ) elements seen so far. Any element larger than the heap maximum cannot belong to the smallest ( k ). At the end, the heap contains exactly those ( k ) elements, which are then sorted.

Complexity

Total:

( O(n \log k) )

Space:

( O(k) )

Alternative (Quickselect based)

1. Use selection (Quickselect) to partition around the ( k )-th smallest element
2. Sort only the first ( k ) elements

This gives:

• Partition: ( O(n) ) average
• Sort prefix: ( O(k \log k) )

Better when ( k \ll n )

When to Use

Use partial sort when:

• You need top ( k ) smallest or largest elements
• Full ordering is unnecessary
• ( k ) is much smaller than ( n )

Common in ranking, streaming analytics, and search systems.