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.

Stalin sort

Class	Sorting
Data structure	Array
Worst-case performance	O(n)
Worst-case space complexity	O(n)

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. ( 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.