Cocktail Shaker Sort
Bidirectional bubble sort that traverses in both directions.
Removes elements that are out of order — the survivors are sorted.
Stalin Sort is a joke sorting algorithm that takes a brutally simple approach to achieving a sorted array: any element that is out of order is eliminated. Rather than rearranging elements into the correct order, the algorithm simply removes elements that do not fit the sorted sequence. The survivors, by definition, form a sorted result -- though the output is typically much shorter than the input.
Stalin Sort is named after Joseph Stalin's authoritarian approach to governance, in which dissent was eliminated rather than addressed. The analogy is darkly humorous: instead of doing the hard work of rearranging elements (resolving disagreements), the algorithm simply purges anything that does not conform to the expected order. The algorithm gained popularity on social media and programming humor forums around 2019, particularly on Twitter and Reddit, where developers shared implementations in various programming languages with commentary about its "efficiency" and its political satire.
For example, given the input [1, 5, 3, 4, 2, 7, 6], Stalin Sort would produce [1, 5, 7]. The elements 3, 4, 2, and 6 are eliminated because they are each less than the running maximum at the time they are encountered.
| Case | Time | Space |
|---|---|---|
| All | O(n) | O(n) |
Stalin Sort runs in O(n) time because it makes exactly one pass through the array. The space complexity is O(n) for the output array, though in-place variants can achieve O(1) extra space by overwriting the input array. The best case for output size occurs when the input is already sorted (all elements are kept), and the worst case occurs when the input is reverse-sorted (only the first element survives).
A correct sorting algorithm must produce a permutation of the input -- the output must contain exactly the same elements as the input, just in sorted order. Stalin Sort violates this fundamental requirement by discarding elements. The output is sorted, but it is not a rearrangement of the input. This makes Stalin Sort a filter, not a sort. It is equivalent to finding the longest non-decreasing subsequence starting from the first element (though not the longest overall, which is a harder problem).
Interestingly, Stalin Sort relates to a well-studied problem in computer science: the Longest Increasing Subsequence (LIS). Stalin Sort finds a non-decreasing subsequence that starts with the first element and greedily extends it. However, this greedy approach does not find the longest such subsequence -- the true LIS problem requires dynamic programming and runs in O(n log n) time. Stalin Sort's greedy approach is much simpler but produces a shorter result because it is anchored to the first element and makes locally optimal choices.
Several humorous variants of Stalin Sort have been proposed. "Recursive Stalin Sort" applies Stalin Sort repeatedly until the output stops changing, though this still loses data. "Democratic Stalin Sort" takes a majority vote on which elements to keep. "Reverse Stalin Sort" eliminates elements that are too large rather than too small. These variants are all jokes, but they illustrate how the core concept can be twisted in creative ways.
Stalin Sort should never be used for actual sorting because it destroys data. It exists purely as programming humor and political satire. Its educational value lies in illustrating the importance of correctness requirements in algorithm design -- specifically, that a sorting algorithm must produce a permutation of its input. It also serves as a fun conversation starter about the difference between filtering and sorting, and about what makes an algorithm "correct."