K-Distribution Sort applied to the push-swap problem

Part I — Push-Swap: A Minimalist Sorting Challenge Using Two Stacks

The goal of this article is to present a sorting algorithm for the push-swap problem that is clear, simple to understand, and easy to implement, while already delivering strong native performance without relying on advanced optimizations. The proposed method focuses on algorithmic clarity and structural elegance, resulting in very compact code that remains efficient on large input sizes.

Purpose

The push-swap project is a sorting challenge that requires sorting a list of integers using only two stacks and a restricted set of operations. The goal is to generate the shortest possible sequence of instructions to sort the initial stack, under tight algorithmic and structural constraints. Despite its simple rule set, push-swap demands efficient strategies, as naive approaches quickly lead to suboptimal results.

Push-swap purpose

Primitives

The operations in push-swap are based on fundamental stack behaviors:

• **push**: places an element on top of a stack.
• **pop**: removes the top element from a stack.
• **swap**: exchanges the two elements at the top.
• **rotate**: shifts all elements upward by one position; the top moves to the bottom.
• **reverse rotate**: shifts all elements downward by one; the bottom moves to the top.

These primitives form the entire vocabulary for transforming an unsorted stack into a sorted one under strict constraints.

Stack primitives

Allowed operations

The sorting must be performed using only the following predefined operations:

Swap

• sa: swap the top two elements of stack A
• sb: swap the top two elements of stack B
• ss: perform both sa and sb simultaneously

Push

• pa: pop the top element from stack B and push it onto stack A
• pb: pop the top element from stack A and push it onto stack B

Rotate (upward)

• ra: shift all elements of stack A up by one (top becomes bottom)
• rb: same for stack B
• rr: perform both ra and rb simultaneously

Reverse Rotate (downward)

• rra: shift all elements of stack A down by one (bottom becomes top)
• rrb: same for stack B
• rrr: perform both rra and rrb simultaneously

Each operation counts as a single instruction and must be printed exactly as shown to standard output.

Part II — The K-Distribution Sort

Overview:

The K-Distribution Sort is a heuristic algorithm tailored for the push-swap sorting problem. It operates by iteratively pushing elements from stack A to stack B, using a growing threshold to decide which elements to transfer and how to place them within B. The technique is particularly known for shaping stack B into a "K-like" structure when visualized—hence the name.

Mechanism:

Let index(i) be the normalized index of each element in stack A (from 0 to n-1).

We define a dynamic threshold window controlled by a parameter delta:

threshold = 0;
while A is not empty:
    if A.head.index <= threshold + delta:
        push A → B
        if A.head.index <= threshold:
            rotate B
        threshold++
    else:
        rotate A

• Elements with index ≤ threshold are pushed then rotated in B, effectively moving them toward the bottom.
• Elements with threshold < index ≤ threshold + delta are pushed without rotation, staying near the top of B.
• All others are skipped with a rotation in A.

Heuristic Behavior:

This strategy encourages value stratification in stack B:

• Low-index (small) values accumulate in the center/bottom of B.
• High-index (large) values accumulate near the top and bottom, due to deferred pushing.
• This naturally forms a visual shape in B resembling the letter K, especially when stack B is represented as a vertical list.

Why K-shape?

Because of the dual-path:

• Low values are pushed early and rotated down, forming the lower leg of the K.
• Mid values are pushed later and remain at the top — center stroke.
• High values rotate in A until they become small enough to be pushed, then settle differently — upper leg.

K-Shape

Heuristic Rationale for Delta (Δ)

The Δ parameter plays a critical role in the K-Distribution Sort strategy. It controls the granularity of the progressive threshold used when pushing elements from stack A to stack B.

• Smaller Δ values yield a more ordered distribution in B, as smaller elements are pushed earlier and rotated deeper. This tends to produce a nearly sorted B (visually forming the diagonal stem of the “K”), resulting in a low-cost B→A reconstruction. However, this comes at the expense of a more expensive A→B phase due to the increased number of rotations and comparisons.
• Larger Δ values reduce the number of operations needed to push from A to B by accepting larger value ranges per threshold step. This speeds up the first phase, but the resulting B is more chaotic, which leads to a costlier and less predictable B→A reconstruction.

Delta

The empirical formula:

Δ = ⌊n / 20⌋ + 7

where n is the initial size of stack A, strikes a practical balance between both extremes. It ensures:

• A progressive structuring of B that visually forms the characteristic “K” shape.
• A well-distributed workload across both phases of the sort.
• Robustness across a wide range of input sizes without requiring tuning.

This heuristic has proven effective in achieving a good trade-off between operation count and sorting regularity in the push_swap constraint model.

Complexity and Applications:

• It is not optimal in terms of moves, but it greatly reduces chaos in B.
• The K-shape makes greedy or ordered reintegration (B→A) easier and faster.
• Best suited for n ∈ [50, 500] elements in push_swap projects, though it remains effective and reliable for a broader range from around 10 to 1000 elements.

Algorithm — K-Distribution Sort

The following pseudocode presents the core logic of the K-Distribution Sort, which incrementally pushes values from stack A to stack B using a dynamic threshold and a tunable delta parameter. This strategy balances order in stack B against the cost of transitions.

void K_Distribution_Sort(Stack *a, Stack *b)
{
    int n = a->size;
    int delta = n / 20 + 7;
    int threshold = 0;
    while (!is_empty(a))
    {
        if (a->top->index <= threshold + delta)
        {
            push(a, b);           // pb
            if (b->top->index <= threshold)
                rotate(b);        // rb
            threshold++;
        }
        else
        {
            rotate(a);            // ra
        }
    }
}

Notes:

• Stack is a structure with pointers to nodes, each of which holds a unique index corresponding to the final sorted order.
• push(a, b) removes the top element from stack a and pushes it onto stack b.
• rotate(x) performs a cyclic rotation: the top becomes the bottom.

This routine progressively builds stack B into a semi-ordered structure with lower-index elements concentrated near the bottom. The resulting distribution optimizes the subsequent reintegration phase.

Part III — Finalize the push-swap

Naive Reintegration: B → A (Greedy Max Selection)

void Reintegration_Sort(Stack *a, Stack *b)
{
    while (!is_empty(b))
    {
        int max_index = find_max_index(b);
        int pos = position_of_index(b, max_index);
        if (pos <= b->size / 2)
        {
            while (b->top->index != max_index)
                rotate(b);       // rb
        }
        else
        {
            while (b->top->index != max_index)
                reverse_rotate(b);  // rrb
        }
        push(b, a);  // pa
    }
}

This method simply retrieves the largest element in stack B at each step and pushes it to stack A. To minimize operations:

• If the max element is in the top half of B, it uses rb to bring it up.
• If it’s in the bottom half, it uses rrb.
• Once the element is at the top, it is pushed with pa.

The result is that stack A gradually builds up in descending order, which, given the constraints of push-swap, is the final desired configuration.

This strategy is naive but effective when stack B already has a semi-sorted structure — such as the one produced by the K-distribution phase.

[embed]K-Shape naive but efficient sort

Auxiliary Functions

Reindexing

void reindex(Node *nodes, int size)
{
    for (int i = 0; i < size; i++)
    {
        int rank = 0;
        for (int j = 0; j < size; j++)
        {
            if (nodes[j].value < nodes[i].value)
                rank++;
        }
        nodes[i].index = rank;
    }
}

Explanation: Assigns an index to each node based on its rank in sorted order, without changing original values or using dynamic memory. This normalization simplifies sorting logic by providing compact, sequential indexes (0..n-1).

Finding the Maximum Index

int find_max_index(Stack *s)
{
    int max = s->top->index;
    Node *node = s->top;
    while (node)
    {
        if (node->index > max)
            max = node->index;
        node = node->next;
    }
    return max;
}

Explanation: Returns the highest index value currently present in the stack.

Finding the Position of a Given Index

int position_of_index(Stack *s, int target_index)
{
    Node *node = s->top;
    int position = 0;
    while (node)
    {
        if (node->index == target_index)
            return position;
        node = node->next;
        position++;
    }
    return -1;
}

Explanation: Returns the position (distance from the top) of the node containing the specified index within the stack, or -1 if the index is not found.

Conclusion

The algorithm presented in this article offers a pragmatic and elegant approach to solving the push-swap problem. With just a handful of well-chosen operations and a compact implementation, it achieves remarkably efficient behavior — even without any additional optimizations.

By relying on reindexing, simple stack manipulation, and a clever heuristic distribution strategy (K-Distribution), this method strikes a balance between clarity, performance, and code brevity.

Its strength lies precisely in its minimalism: short, readable, and easy to implement — making it an ideal choice for both learning and competition.

Beyond its simplicity, this algorithm opens the door to further optimizations. First, the second phase (from stack B back to A) can be made more efficient by introducing cost-based decision logic, selecting the element to move based on its total rotation cost. Second, once the full command list is generated, a post-processing pass can simplify it: sequences like pa followed immediately by pb can cancel out, and simultaneous operations like ra + rb can be merged into a single rr, significantly reducing the total number of instructions without altering the result.

For more advanced programmers aiming for optimal performance, more aggressive strategies can be employed. Rather than relying solely on raw movement cost, one can introduce weighted heuristics — assigning bonuses or penalties based on patterns, expected impact, or positional context within the stacks. These weights can be derived from harmonic means, ratios, or even intentionally chaotic functions, which, though unpredictable, may help escape local minima and yield shorter solutions through better global arrangements.

Additionally, a deeper post-processing phase can detect and compress longer instruction patterns: for example, repeated sequences like ra ra ra rb rb rb can be merged into rr rr rr.

It is also possible to enhance the K-distribution strategy itself by dividing stack A into dynamic chunks, where each chunk is progressively smaller — allowing finer control and increased ordering as the process advances. These variable-size segments can further improve the structure of B and facilitate a more efficient reintegration phase.

In the end, the goal is not to find a solution quickly, but to produce the most concise and efficient list of operations possible, where controlled complexity often leads to elegance.

[embed]Optimized chunked K-Shape