Stalin sort
| Class | Sorting |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n) |
| Worst-case space complexity | O(n) |
Stalin sort is a stable sorting algorithm that works by iterating over the array of elements to be sorted and removing items that are "out of order"[1] in the array to be sorted. It is a method to find the longest increasing subsequence in a given array. The sort is considered to be a humourous algorithm, not being intended to be used to sort in real-life applications.
The algorithm can be described by the following pseudocode.[2]
function stalinSort(list A) is
n = length(A)
bigger = 0
B = empty list
for i = 0 to n - 1
if A[i] >= bigger THEN
bigger = A[i]
B.push(A[i])
return B
Example
Consider the unsorted array "1 2 5 3 10 4 7 6", to be sorted into increasing order. In each step, elements written in bold are being compared. In this example two items in the array need to be removed.
- ( 1 2 5 3 10 4 ) → ( 1 2 5 3 10 4 ), Here the items being compared are in increasing order and hence are unchanged.
- ( 1 2 5 3 10 4 ) → ( 1 2 5 3 10 4 )
- ( 1 2 5 3 10 4 ) → ( 1 2 5 10 4 ), Since 3 < 5, 3 is removed from the array.
- ( 1 2 5 10 4 ) → ( 1 2 5 10 4 )
- ( 1 2 5 10 4 ) → ( 1 2 5 10 4 ), As 4 < 10, 4 is removed from the array.
- ( 1 2 5 10), Here the algorithm terminates as the end of the array has been reached.
References
- ↑ Paula, Gustavo de (2025-07-30), gustavo-depaula/stalin-sort, retrieved 2025-08-02
- ↑ Ivanchikov, M. M.; et al. (4 August 2025). "https://rep.bntu.by/bitstream/handle/data/155707/311-312.pdf?sequence=1" (PDF). Retrieved 4 August 2025. External link in
|title=(help)
External links
- A "Sorting" algorithm, Stalin Sort being used for code golfing.
- Visualisation by Kyle Smith
This article "Stalin sort" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Stalin sort. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
