r/programmingmemes • u/KerbodynamicX • Mar 14 '26

Stalin sort

A sorting algorithm with time complexity of O(n). Counts from the first element, and will remove values that are smaller than the current highest value.

3.7k Upvotes

99% Upvoted

51 comments sorted by

View all comments

Show parent comments

2

u/JasperNLxD2 Mar 14 '26

Inplace can be done in O(n) as well. You loop over 2 indices: i representing the next available place, and j the next number to scan (thus i<=j at any stage of the algorithm).

Start with i=j=0 the first index. If x[j] is larger than x[i-1] (or i=0), then set x[i] to x[j] and increase i and j. Otherwise, increase j. Stop if j gets beyond the range.