Stalin Sort
Algorithm 1
Let’s say we have an array of length $n$. If we read the array from the beginning to the end and repeatedly remove elements where the element behind is greater than the one in front, we ‘in order’ obtain a sorted array. Its time complexity is $O(n)$, and the pseudocode is as follows.
FUNCTION stalinSort(A : list OF sortable items)
n := length(A)
bigger := 0
B SET empty list
FOR i := 0 TO n NOT inclusive DO
IF A[i] >= bigger THEN
bigger := A[i]
B.push(A[i])
END IF
END FOR
RETURN B
END FUNCTION
Description
Stalin Sort is an algorithm named after the Soviet dictator Joseph Stalin. It’s more of a joke than a real sorting algorithm because it removes elements that don’t align, much like Stalin did by sending them to the Gulag, hence the elements of the original array do not remain intact.
However, surprisingly, there might be situations in coding when such an algorithm is necessary or sufficient. Fortunately, due to its brilliant naming and simple implementation, there’s no real need to make an effort to remember it.