Stalin sort

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 

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. ( 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.
2. ( 1 2 5 3 10 4 ) → ( 1 2 5 3 10 4 )
3. ( 1 2 5 3 10 4 ) → ( 1 2 5 10 4 ), Since 3 < 5, 3 is removed from the array.
4. ( 1 2 5 10 4 ) → ( 1 2 5 10 4 )
5. ( 1 2 5 10 4 ) → ( 1 2 5 10 4 ), As 4 < 10, 4 is removed from the array.
6. ( 1 2 5 10), Here the algorithm terminates as the end of the array has been reached.

• A "Sorting" algorithm, Stalin Sort being used for code golfing.
• Visualisation by Kyle Smith