# Bingo Sort

# Bingo Sort

Bingo sort is a selection-style sorting algorithm that handles duplicate values efficiently. Instead of selecting one minimum value per pass, it selects the current minimum value and moves all of its occurrences into the sorted prefix.

This makes it useful for inputs with many repeated values.

## Problem

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

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

## Key Idea

Maintain a sorted prefix. At each pass, find the smallest value remaining in the unsorted suffix. Move every occurrence of that value into the next positions of the prefix. Then continue with the next distinct value.

## Algorithm

```id="k8x2p4"
bingo_sort(A):
    n = length(A)
    start = 0

    while start < n:
        bingo = minimum value in A[start..n-1]

        next_value = infinity
        i = start

        while i < n:
            if A[i] == bingo:
                swap(A[i], A[start])
                start = start + 1
            else:
                if A[i] < next_value:
                    next_value = A[i]
                i = i + 1
```

## Example

Let

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

First pass finds minimum $1$ and moves all $1$s to the front:

$$
[1, 1, 1, 4, 2, 3]
$$

Next pass finds $2$:

$$
[1, 1, 1, 2, 4, 3]
$$

Next pass finds $3$:

$$
[1, 1, 1, 2, 3, 4]
$$

## Correctness

At each pass, the algorithm places every occurrence of the smallest remaining value into the next positions of the sorted prefix. Therefore the prefix is sorted and contains exactly the smallest values seen so far. When the prefix reaches length $n$, all values have been placed in nondecreasing order.

## Complexity

Let $d$ be the number of distinct values.

| case            |     time |
| --------------- | -------: |
| many duplicates |  $O(nd)$ |
| all equal       |   $O(n)$ |
| all distinct    | $O(n^2)$ |

Space complexity:

$$
O(1)
$$

## Properties

* in-place
* not stable
* efficient when duplicates are common
* selection-sort variant

## When to Use

Bingo sort is useful when the input contains many duplicate values and memory must remain constant. For general-purpose sorting, counting sort is better when the key range is small, and comparison sorts are better for arbitrary data.

## Implementation

```id="m3x9q2"
def bingo_sort(a):
    n = len(a)
    start = 0

    while start < n:
        bingo = min(a[start:])

        i = start
        while i < n:
            if a[i] == bingo:
                a[i], a[start] = a[start], a[i]
                start += 1
            else:
                i += 1

    return a
```

```id="z6k2v8"
func BingoSort(a []int) {
    n := len(a)
    start := 0

    for start < n {
        bingo := a[start]
        for i := start + 1; i < n; i++ {
            if a[i] < bingo {
                bingo = a[i]
            }
        }

        for i := start; i < n; {
            if a[i] == bingo {
                a[i], a[start] = a[start], a[i]
                start++
            } else {
                i++
            }
        }
    }
}
```