Top K Sort

Top K sort finds the ( k ) smallest or largest elements and returns them in sorted order. Unlike full sorting, it avoids ordering the entire dataset.

You use it when only the best ( k ) items matter, such as ranking, search results, or recommendation systems.

Problem

Given an array ( A ) of size ( n ) and integer ( k ), compute:

• the smallest ( k ) elements in sorted order or
• the largest ( k ) elements in sorted order

Algorithm (Min heap for largest k)

To find largest ( k ), maintain a min heap of size ( k ):

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

2. For each remaining element:

   • If it is larger than heap minimum, replace it

3. Extract and sort heap

top_k_largest(A, k):
    heap = min_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

For smallest ( k ), use a max heap instead.

Example

Let:

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

Largest 2 elements:

( [9, 8] )

Sorted output:

( [8, 9] )

Correctness

The heap maintains exactly the best ( k ) elements seen so far. Any element worse than the heap boundary cannot belong to the top ( k ), so it is discarded.

Complexity

Total:

( O(n \log k) )

Space:

( O(k) )

Alternative (Quickselect)

1. Partition array around the ( k )-th largest element
2. Sort only the selected ( k ) elements

Cost:

• average ( O(n) ) partition
• ( O(k \log k) ) final sort

When to Use

Top K sort is appropriate when:

• you need ranked results
• ( k \ll n )
• full sorting would waste time

This pattern appears in search engines, analytics pipelines, and streaming systems where only the highest scoring items are relevant.