Double Selection Sort

Double selection sort improves selection sort by selecting both the minimum and maximum elements in each pass. It places the minimum at the beginning and the maximum at the end, reducing the number of passes by roughly half.

Problem

Given a sequence $A$ of length $n$, reorder it such that

$$ A[0] \le A[1] \le \cdots \le A[n-1] $$

Algorithm

Maintain two boundaries, left and right. In each pass, scan the range $[left, right]$ to find both the minimum and maximum elements, then place them at the correct positions.

double_selection_sort(A):
    left = 0
    right = length(A) - 1

    while left < right:
        min_index = left
        max_index = right

        for i from left to right:
            if A[i] < A[min_index]:
                min_index = i
            if A[i] > A[max_index]:
                max_index = i

        swap(A[left], A[min_index])

        if max_index == left:
            max_index = min_index

        swap(A[right], A[max_index])

        left = left + 1
        right = right - 1

Example

Let

$$ A = [7, 2, 5, 1, 9, 3] $$

Pass 1:

• min = 1 → position 0
• max = 9 → position 5

→ [1, 2, 5, 7, 3, 9]

Pass 2:

• min = 2 → position 1
• max = 7 → position 4

→ [1, 2, 5, 3, 7, 9]

Continue until sorted:

$$ [1, 2, 3, 5, 7, 9] $$

Correctness

Each pass places the smallest remaining element at the left boundary and the largest at the right boundary. The unsorted region shrinks from both sides, and the invariant that the outer segments are sorted holds throughout.

Complexity

case	comparisons	time
best	$\frac{n(n-1)}{2}$	$O(n^2)$
worst	$\frac{n(n-1)}{2}$	$O(n^2)$
average	$\frac{n(n-1)}{2}$	$O(n^2)$

Space complexity:

$$ O(1) $$

Properties

• in-place
• not stable
• fewer passes than standard selection sort

When to Use

This variant reduces the number of passes, which can slightly improve performance when scanning cost dominates. However, it still performs $O(n^2)$ comparisons and is mainly of educational interest.

Implementation

def double_selection_sort(a):
    left = 0
    right = len(a) - 1

    while left < right:
        min_idx = left
        max_idx = right

        for i in range(left, right + 1):
            if a[i] < a[min_idx]:
                min_idx = i
            if a[i] > a[max_idx]:
                max_idx = i

        a[left], a[min_idx] = a[min_idx], a[left]

        if max_idx == left:
            max_idx = min_idx

        a[right], a[max_idx] = a[max_idx], a[right]

        left += 1
        right -= 1

    return a

func DoubleSelectionSort[T constraints.Ordered](a []T) {
    left := 0
    right := len(a) - 1

    for left < right {
        minIdx := left
        maxIdx := right

        for i := left; i <= right; i++ {
            if a[i] < a[minIdx] {
                minIdx = i
            }
            if a[i] > a[maxIdx] {
                maxIdx = i
            }
        }

        a[left], a[minIdx] = a[minIdx], a[left]

        if maxIdx == left {
            maxIdx = minIdx
        }

        a[right], a[maxIdx] = a[maxIdx], a[right]

        left++
        right--
    }
}