📂Algorithm

Stalin Sort

Algorithm ¹

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.