# Partial Sort

# 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

```id="9a2f1c"
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

| phase          | cost               |
| -------------- | ------------------ |
| build heap     | ( O(k) )           |
| scan remaining | ( O((n-k)\log k) ) |
| output sort    | ( O(k \log k) )    |

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.