## Stalin Sort

### January 19, 2021

Stalin Sort is a single-pass sort that operates in O(1) space and O(*n*) time. Iterate down the list of elements checking if they are in order. Any element which is out of order is sent to the gulag (eliminated from the list). At the end you have a sorted list, though it may not be a permutation of the original list. As an example, the list (1 2 5 3 5 7) is Stalin-sorted as (1 2 5 5 7); the 3 is dropped because it is less than the 5 that it follows.

Your task is to write a program that implements Stalin sort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here is an implementation in R7RS Scheme using filter-map from SRFI 1.

Here’s a R7RS Scheme implementation, a fix to my earlier oopsie posting.

Here is my take on this, using Julia 1.5.x: https://pastebin.com/fYD31uep

I wonder if there is a practical application of this algo. Cheers!

Here’s a solution in Racket:

Sample output:

Klong

Clojure:

(first (reduce (fn [[elems last] cur] (if (>= cur last) [(conj elems cur) cur] [elems last])) [[] 0] [1 2 5 3 4 7]))

Or a bit more complete solution that takes in account negative numbers:

#(first (reduce (fn [[elems last] cur] (if (>= cur last) [(conj elems cur) cur] [elems last])) [[] (first %)] %))

Klong (earlier version did not work correctly for all inputs)

@ProgrammingPraxis: What does O(1) space and O(n) time mean? Thanks, Steve

@bookofstevegraham: O(1) space means the program, at runtime, uses a constant amount of space that does not depend on the size of the input. O(n) time means the runtime is proportional to the size of the input. Big-O notation is a simple means of comparing the complexity of two algorithsm.

@ProgrammingPraxis: Thanks. So I understand that you have to modify the first list itself and not create a 2nd one to receive the result.

@bookofstevegraham: No, you could also build the result in a new list and discard the original, as I did.

@programingpraxis: Thanks. I did that in my last submission.