r/programminghumor

Ngl it's kinda gay.

Anyways here's the pseudocode for N partition version

procedure GaySort(A[], low, high):
    // Base case: surrender
    if high - low <= 0:
        return

    // Step 1: Partition into k sub-arrays (k = 2, 3, or 4)
    pivots[] := PartitionK(A[], low, high)
    // pivots[] contains the final sorted positions of k-1 pivot elements
    // This creates k sub-arrays between them

    // Step 2: Recursively sort each sub-partition
    // (wasteful first pass — we're about to throw it all away)
    prev := low
    for each pivot in pivots[]:
        GaySort(A[], prev, pivot - 1)
        prev := pivot + 1
    GaySort(A[], prev, high)             // sort final sub-partition

    // Step 3: Find the maximum across all sub-partitions
    // (each sub-partition's max is its last element, since we just sorted them)
    max_idx := FindMax(A[], low, high)

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

    // Step 5: Re-sort everything except the placed max
    // (this makes the previous recursive calls completely pointless)
    GaySort(A[], low, high - 1)

and the the partition 2 variant:

procedure GaySort(A[], low, high):
    // Base case: surrender
    if high - low <= 0:
        return

    // Step 1: Partition into 2 sub-arrays using max as right pivot
    pivot := Partition2(A[], low, high)
    // pivot contains the final sorted position of the max element
    // This creates 2 sub-arrays: [low..pivot-1] and [pivot+1..high]
    // Note: right partition [pivot+1..high] is always empty since pivot = max

    // Step 2: Recursively sort each sub-partition
    // (wasteful first pass — we're about to throw it all away)
    GaySort(A[], low, pivot - 1)
    // GaySort(A[], pivot + 1, high) -- always empty, pivot is max

    // Step 3: Find the maximum across all sub-partitions
    // (each sub-partition's max is its last element, since we just sorted them)
    // Note: max is already at A[pivot] == A[high] since pivot = max
    max_idx := pivot

    // Step 4: Swap max to the end of the current range
    // Note: already there, this is a no-op
    swap(A[max_idx], A[high])

    // Step 5: Re-sort everything except the placed max
    // (this makes the previous recursive calls completely pointless)
    GaySort(A[], low, high - 1)