Stalin sort

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

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 2 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 been reached.

External links

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