# Stable Quicksort

# Stable Quicksort

Stable quicksort modifies the standard quicksort to preserve the relative order of equal elements. Standard quicksort is not stable because partitioning swaps elements arbitrarily.

To achieve stability, the algorithm avoids in-place swaps and instead builds ordered partitions.

## Problem

Given an array $A$ of length $n$, reorder it such that:

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

and for any equal elements $A[i] = A[j]$ with $i < j$, their relative order remains unchanged.

## Idea

Instead of partitioning in-place, divide the array into three lists:

* elements less than the pivot
* elements equal to the pivot
* elements greater than the pivot

Preserve the original order when constructing these lists.

Then recursively sort the left and right parts and concatenate:

$$
\text{sorted left} + \text{equal} + \text{sorted right}
$$

## Algorithm

```text id="f3q8xa"
stable_quicksort(A):
    if length(A) <= 1:
        return A

    pivot = choose_pivot(A)

    left = []
    equal = []
    right = []

    for x in A:
        if x < pivot:
            append x to left
        else if x > pivot:
            append x to right
        else:
            append x to equal

    return stable_quicksort(left) + equal + stable_quicksort(right)
```

## Example

Let:

$$
A = [(3,a), (1,x), (3,b), (2,y)]
$$

Sort by the first component.

Partition:

| group | elements       |
| ----- | -------------- |
| < 3   | [(1,x), (2,y)] |
| = 3   | [(3,a), (3,b)] |
| > 3   | []             |

Recursive sort:

$$
[(1,x), (2,y)] + [(3,a), (3,b)]
$$

The relative order of $(3,a)$ and $(3,b)$ is preserved.

## Correctness

Partitioning divides elements into three groups while maintaining their original order inside each group. Recursive calls sort the left and right groups. Concatenation produces a sorted sequence with stability preserved.

## Complexity

| case    | time          |
| ------- | ------------- |
| best    | $O(n \log n)$ |
| average | $O(n \log n)$ |
| worst   | $O(n^2)$      |

Space:

$$
O(n)
$$

due to additional lists.

## Properties

| property         | value |
| ---------------- | ----- |
| stable           | yes   |
| in-place         | no    |
| comparison based | yes   |
| simplicity       | high  |

## Notes

Stable quicksort trades memory for stability. In practice, merge sort or Timsort is usually preferred when stability is required, since they achieve stability with better guarantees.

This version is mainly useful for conceptual understanding or when quicksort style partitioning must be preserved.

## Implementation

```python id="z6p4tn"
def stable_quicksort(a):
    if len(a) <= 1:
        return a

    pivot = a[len(a) // 2]

    left = []
    equal = []
    right = []

    for x in a:
        if x < pivot:
            left.append(x)
        elif x > pivot:
            right.append(x)
        else:
            equal.append(x)

    return stable_quicksort(left) + equal + stable_quicksort(right)
```

```go id="y2s8mc"
func StableQuickSort(a []int) []int {
	if len(a) <= 1 {
		return a
	}

	pivot := a[len(a)/2]

	left := []int{}
	equal := []int{}
	right := []int{}

	for _, x := range a {
		if x < pivot {
			left = append(left, x)
		} else if x > pivot {
			right = append(right, x)
		} else {
			equal = append(equal, x)
		}
	}

	left = StableQuickSort(left)
	right = StableQuickSort(right)

	return append(append(left, equal...), right...)
}
```