Lazy Selection Sort

Lazy selection sort produces sorted output incrementally. Instead of sorting the entire array, it finds the next smallest element only when requested.

You use it when you need a few smallest elements or when output is consumed step by step.

Problem

Given an array ( A ), support an operation:

• next() that returns the next smallest element

without sorting the entire array in advance.

Idea

Keep track of which elements have already been selected. Each call scans the remaining elements to find the next minimum.

This defers work and avoids unnecessary comparisons if only part of the sorted order is needed.

Algorithm

lazy_selection(A):
    used = array of false of size n

    function next():
        min_val = +infinity
        min_idx = -1

        for i in 0..n-1:
            if not used[i] and A[i] < min_val:
                min_val = A[i]
                min_idx = i

        if min_idx == -1:
            return null

        used[min_idx] = true
        return min_val

Example

Input:

[ A = [4, 1, 3, 2] ]

Calls:

next() -> 1
next() -> 2
next() -> 3

The array is never fully sorted in memory, but values are returned in sorted order.

Correctness

At each call, the algorithm scans all unused elements and selects the smallest among them. Since previously selected elements are marked and excluded, each returned value is the next smallest in the total order.

Complexity

Let ( k ) be the number of calls.

Space:

[ O(n) ]

Optimization (Heap Based)

Using a min heap improves performance:

build_heap(A)

next():
    return heap.pop()

This yields:

• build: ( O(n) )
• each next: ( O(\log n) )

When to Use

Use lazy selection sort when:

• only a few smallest elements are needed
• full sorting is unnecessary
• simplicity matters more than performance

For larger ( k ), heap-based or partial sort methods are more efficient.