Gay sort

GaySort is a recursive sorting algorithm first conceptualized by user jdoexbox360 in a Discord server for their Data Structures and Algorithms course at Arizona State University.

The algorithm combines a multi-pivot quicksort partitioning phase with a selection sort elimination phase. Because the partitioning step's output is not consumed before a full re-sort is initiated in a subsequent step, the partitioning step does not affect the algorithm's output. GaySort has been informally compared to Slowsort, whose authors described their own algorithm's approach as "multiply and surrender." The algorithm's time complexity is O(n²logn) in the general case, degrading to O(n⋅2ⁿ) when the pivot is always chosen as the maximum element of the current range.

Description

Algorithm

GaySort operates on a mutable array A[] over a subrange [low, high]. At each level of recursion, the algorithm performs five steps:

1. Partition A[low..high] into k sub-arrays using k−1 pivots (k ∈ {2, 3, 4}), placing each pivot at its final sorted position. This step follows the structure of multi-pivot quicksort.
2. Recursively sort each of the k sub-arrays produced in step 1, mirroring the recursive descent of standard quicksort.
3. Scan A[low..high] to locate the index of the maximum element. The scan is performed over the full range regardless of the structure established by steps 1 and 2.
4. Swap the maximum element to A[high], placing it in its final sorted position, consistent with the selection sort invariant.
5. Recurse on A[low..high−1], excluding the newly placed maximum.

Pseudocode

The following pseudocode describes the 2-pivot variant, with the maximum element used as the right pivot:

procedure GaySort(A[], low, high):
    // Base case: surrender
    if high − low ≤ 0:
        return

    // Step 1: Partition using max as right pivot
    pivot := Partition2(A[], low, high)
    // right sub-array always empty; pivot = max

    // Step 2: Recurse on left sub-array
    GaySort(A[], low, pivot − 1)

    // Step 3: Max already at A[pivot] = A[high]
    max_idx := pivot

    // Step 4: Swap max to end
    swap(A[max_idx], A[high])

    // Step 5: Re-sort remainder
    GaySort(A[], low, high − 1)

Redundancy of step 2

Step 3 scans the full range [low, high] without using the sorted structure produced by step 2, and step 5 re-invokes GaySort over the same range, re-partitioning data that step 2 had already sorted. As a result, step 2 can be removed without changing the algorithm's output or correctness.

Without step 2, the algorithm is equivalent to recursive selection sort: locate the maximum, place it at the end of the current range, and recurse on the remainder.

Complexity

General case

Let T(n) denote the number of comparisons on an input of size n. Each call to GaySort performs k · T(n/k) comparisons from step 2, T(n−1) from step 5, and O(n) from partitioning and scanning, yielding the recurrence relation:

T(n) = k·T(n/k) + T(n−1) + O(n)

Unrolling the T(n−1) chain yields n levels, each spawning a k·T(n/k) sub-problem of size approximately n. By the master theorem, each such sub-problem costs O(n log n). Summing over n levels:

T(n) = O(n · n log n) = O(n² log n)

This exceeds the O(n²) cost of the selection sort the algorithm reduces to when step 2 is removed.

Maximum-element pivot (2-pivot variant)

When the right pivot is always the maximum of the current range, Partition2 always places the pivot at A[high], leaving the right sub-array empty. Step 2 then reduces from k·T(n/k) to a single call T(n−1), giving:

T(n) = 2·T(n−1) + O(n)

This recurrence solves to T(n) = O(n · 2ⁿ), which is superexponential. The divide-and-conquer term, which provided logarithmic depth in the general case, collapses into a second linear recursion, doubling the work at every level.

See also

• Quicksort
• Selection sort
• Slowsort
• Stooge sort
• Master theorem (analysis of algorithms)

References

• Broder, Andrei; Stolfi, Jorge (1984). "Pessimal Algorithms and Simplexity Analysis". ACM SIGACT News.
• Hoare, C. A. R. (1962). "Quicksort". The Computer Journal. 5 (1): 10–16.