# Recursive Stalin Sort [duplicate]

There is a "sorting" algorithm often called Stalin Sort, where instead of sorting an array, you just remove any items that are out of order. In this challenge, you'll implement part of a sorting algorithm which recursively sorts the removed items, then merges the arrays to form one (properly sorted) array.

## Algorithm

Take this array:

[7, 1, 2, 8, 4, 10, 1, 4, 2]


There are a few sets of items you could remove to make it increasing. For this challenge, you should keep the first item the same, even if it doesn't result in the longest possible list of sorted items. This gives us [7, 8, 10], with [1, 2, 4, 1, 4, 2] as the removed items.

If you also do this with the removed items, you get [1, 2, 4, 4], with [1, 2] as the removed items. Because this is also sorted, we're done. This gives us three arrays:

[7, 8, 10]
[1, 2, 4, 4]
[1, 2]


This is the format of the output.

If you wanted to use this to sort the array, you'd recursively merge the last two arrays to form one sorted list:

[1, 1, 2, 2, 4, 4, 7, 8, 10]


Take an array of integers as input. Return all of the arrays of removed items, before they are merged, as shown above.

You can do this by returning a 2d array, or printing any unambiguous representation of the arrays (for example, comma separated numbers and newline separated arrays).

## Test cases

Input: [1, 2]

[1, 2]


Input: [2, 1]

[2]
[1]


Input: [1, 2, 4, 1, 2]

[1, 2, 4]
[1, 2]


Input: [2, 1, 1, 2, 2]

[2, 2, 2]
[1, 1]


Input: [1, 2, 4, 8, 4, 2, 1]

[1, 2, 4, 8]
[4]
[2]
[1]


Input: [8, 4, 2, 1, 2, 4, 8]

[8, 8]
[4, 4]
[2, 2]
[1]


Input: [7, 1, 2, 8, 4, 10, 1, 4, 2]

[7, 8, 10]
[1, 2, 4, 4]
[1, 2]


Input: [7, 7, 8, 7, 7]

[7, 7, 8]
[7, 7]


## Other

This is , so shortest answer (in bytes) per language wins!

• Can we assume positive integers? Oct 7, 2021 at 21:54
• @emanresuA I guess so, since that's all I use in my examples. (and handling negative integers doesn't add much to this challenge) Oct 7, 2021 at 21:56
• There's however a test case with 0's. So, it's currently non-negative integers rather than positive integers. Oct 8, 2021 at 8:50
• @Arnauld Good point. So I don't invalidate any existing answers, I'll just edit the test cases with 0s and make them another number. Oct 8, 2021 at 13:33
• Suggested test case: [7,7,8,7,7][[7,7,8],[7,7]]. Although I give up for now, the program I was working on worked for all existing test cases, but gave [[7,7,7,7],[8]] for this one.. Oct 11, 2021 at 12:59

# Jelly, 10 bytes

»\nx@µƬœ-Ɲ


Try It Online!

Pleasantly surprised this works without having to stick any reverses in or anything. ḟ"»\FµƬœ-Ɲ also works for the same length. Ultimately the result of trying to replace the ¹ in hyper-neutrino's answer with something else, funnily enough.

     µƬ       Repeat while unique, collecting all results including the input:
n           For each element, is it not equal to
»\            the largest element of the list at that point?
x@         Keep only the non-equal elements, i.e. the "out of order" elements.
Ɲ    For each overlapping pair of adjacent results:
œ-     for each element of the second, remove its last occurrence from the first.


# R, 58 57 bytes

f=function(a,b=a<cummax(a)){any(b)&&f(a[b]);print(a[!b])}


Try it online!

Prints the arrays in reverse order.

Add one byte to print in the same order as the example (try it here):

f=function(a,b=a<cummax(a)){show(a[!b]);if(any(b))f(a[b])}

• what does cummax do? Oct 9, 2021 at 3:26
• @NooneAtAll cumulative maximum = highest value so far at each position in a vector. Oct 9, 2021 at 6:17

# Haskell, 97 90 bytes

f(h:t)=g[h]t[]
f[]=[]
g s[]r=reverse s:f r
g(a:b)(h:t)r|h<a=g(a:b)t\$r++[h]|1>0=g(h:a:b)t r


Try it online!

# Python 3, 88 bytes

f=lambda s:s and[[s.pop(i)for i,x in[*enumerate(s)][::-1]if x==max(s[:i+1])][::-1]]+f(s)


Try it online!

## How it works :

let say our list is [7, 1, 2, 8, 4, 10, 1, 4, 2].

• we iterate through the list backward, poping the items which are the maximum of the list up to them. Here 10 is equal to max of [7, 1, 2, 8, 4, 10], 8 of [7, 1, 2, 8] and 7 of [7]. So we have [10, 8, 7]
• we reverse it to have [7, 8, 10]
• we return it along with the result of the function applied to the remaining items ([1, 2, 4, 1, 4, 2])
• when the list is empty, it returns itself ([])
• You can save 2 bytes if you follow the convention of putting f=\ in the header on tio like this Try it online! Oct 9, 2021 at 2:27
• @MVirts I could if I defined my solution as a anonymous function. But here I have to name it because I recursively call it. So the f= is mandatory Oct 9, 2021 at 19:54
• I see... Not sure if I posted any, but I've definitely neglected this when working on solutions. Oct 11, 2021 at 16:24

# APL (Dyalog Unicode), 21 bytes

Anonymous tacit prefix function.

{m/⍵⊣⎕←⍵/⍨~m←⍵≠⌈\⍵}⍣≡


Try it online!

{}⍣≡ apply the following lambda until stable (i.e. the argument is empty

⌈\⍵ cumulative maximum or argument

⍵≠ Boolean mask indicating which elements of the argument differ

m← assign to m (for mask)

~ invert the mask (lit. logical NOT)

⍵/⍨ filter the argument using that mask

⎕← print that

⍵⊣ ignore that in favour of the argument

m/⍵ filter the argument using the mask m

# K (ngn/k), 17 bytes

{x@.=+(x<|\x*)\1}


Try it online!

Collaborative effort from @ngn, @Bubbler and @chrispsn at the k tree. Assumes positive numbers.

With 2 more bytes it can handle negatives:

{x@.=+~{x*x<|\x}\x}


My original solution:

# K (ngn/k), 27 bytes

f:{{(,x),f y}/x@&'~:\x=|\x}


Try it online!

 f:{{(,x),f y}/x@&'~:\x=|\x}
x=|\x    x equals cumulative max
~:\         append negation
x@&'            partition x using both boolean masks
{(,x),f y}                 join first partition with recursive call on second partition
/                until convergence


# BQN, 21 20 bytesSBCS

-1 byte by omitting 𝕊 in the header for the base case

{⟨⟩:𝕩;𝕊⊸∾⟜<´⌈⊸=⊸⊔𝕩}

{⟨⟩:𝕩;𝕊⊸∾⟜<´⌈⊸=⊸⊔𝕩}
⟨⟩:𝕩;               # If the input is an empty list, return the input, otherwise:
⌈⊸=⊸⊔𝕩  # Group the input by equality with the max scan.
´         # Between the two groups:
𝕊⊸             # recurse on the left group
∾⟜<          # and join to the enclosed right group.


# Jelly, 13 bytes

»\=¹ƙƊṄṛ¥/µÐL


Try It Online!

I think this might be pretty much identical to Adám's answer but I'm not really sure; came up with it independently anyway.

»\=¹ƙƊṄṛ¥/µÐL  Main Link
µÐL  Repeat until the results are no longer unique (which happens when it hits the empty array)
»\             Cumulative maximum; get the largest element so far at each position
=            Vectorizing equality; basically find which elements should be extracted
¹ƙ          Key by identity; separate into groups based on the equality map (the first element will always be included, so we don't have to worry about group ordering)
/     Reduce; since the list will necessarily have two elements, call last dyad on these two
Ṅṛ¥      Combined dyad; print out the left element and return the right element


# Charcoal, 26 bytes

Ｗθ«≔⟦⟧υ≔Φθ∨∧υ‹κ⌈υ¬⊞ＯυκθＩ⟦υ


Try it online! Link is to verbose version of code. Explanation:

Ｗθ«


Repeat until there is nothing left to sort.

≔⟦⟧υ


Start each iteration with an empty result.

≔Φθ∨∧υ‹κ⌈υ¬⊞Ｏυκθ


Push the sorted values to the result while filtering them out from the input list.

Ｉ⟦υ


Output the sorted values, double-spacing between each sorted list.

# Ruby, 51 bytes

f=->a,*b{a[c=0]&&f[a.map{|i|i<c ?i:b<<c=i}-[p(b)]]}


Try it online!

### Commented

f=->a,*b{     # lambda with a = input array, b = empty array
a[  0]&&      # if a is not empty
c=0         # initialise c, the maximum value encountered so far, to 0
f[            # recursively call f
a.map{|i|     # map each element i of a to either:
i<c ?i        # itself, if i<c
:b<<  i       # the array b with i appended, otherwise
c=i       # update c
}             # end of map
-[    ]       # remove from the call to f all elements equal to...
p(b)        # print and return b
]             # end of recursive call
}             # end of lambda


# Wolfram Language (Mathematica), 99 bytes

f=If[#=={},{},Join[{#},f@#2]&@@Fold[Insert[#,#2,{If[#2<#[[1,-1]],2,1],-1}]&,{#[[{1}]],{}},Rest@#]]&


Try it online!

f=
If[#=={},{},           # recursive base case
Join[{#},f@#2]&@@    # append recursive result
Fold[
Insert[#,#2,{If[#2<#[[1,-1]],2,1],-1}]&, # insert onto end of 1st or 2nd list
{#[[{1}]],{}},                           # init 1st list with first input and 2nd list empty
Rest@#                                   # fold across rest of list
]]&


# C (clang), 104 $$\\cdots\$$ 98 96 bytes

k;m;*c;*b;f(*a,l){for(;k=l;)for(m=*(c=b=a);k--;++b)*b<m?*c++=*b:printf("\n%d "+(b>a),m=*b,--l);}


Try it online!

Saved 2 bytes thanks to ceilingcat!!!

Inputs the a pointer to an array of integers and its length (because pointers in C carry no length information).
Prints the recursive stalin sort of the input array to stdout as space separated numbers and newline separated arrays.

# Haskell, 50 bytes

import Data.List
f[]=[]
f x|n<-nubBy(>)x=n:f(x\\n)


Try it online!

I took the brilliant idea of using nubBy(>) to perform a single "Stalin sort" from HPWiz on anagol.

# JavaScript (ES6),  59  57 bytes

f=a=>a+a?[a.filter(v=>a>v?!b.push(v):a=v,b=[]),...f(b)]:a


Try it online!

### Commented

f = a =>             // f is a recursive function taking a[]
a + a ?            // if a[] is not empty:
[ a.filter(v =>  //   for each value v in a[]:
a > v ?      //     if v is less than the last kept element:
!b.push(v) //       discard this value and push it in b[]
:            //     else:
a = v,     //       keep this value and save it in a
b = []       //     start with b[] = empty array
),             //   end of filter()
...f(b)        //   append the result of a recursive call with b[]
]                //
:                  // else:
a                //   stop the recursion

• Redwolf says we can assume positive integers, so you don't have to support 0s Oct 8, 2021 at 8:43

# TI-Basic, 80 bytes

Ans→A
{ʟA(1→B
ʟB→C
For(I,2,dim(ʟA
ʟA(I
If Ans≥ʟB(dim(ʟB
Then
augment(ʟB,{Ans→B
Else
augment(ʟC,{Ans→C
End
End
Disp ʟB
ΔList(cumSum(ʟC
prgmZ

• assumes that the program is stored in prgmZ to allow recursion

• input is taken as Ans to allow recursion

• ʟA is used as the input list, ʟB the cleansed list and ʟC the remaining numbers, with a leading dummy value because TI-Basic can't handle empty lists

• ΔList(cumSum(ʟC basically trims ʟC from its first value and stores it in Ans, to allow calling the program again with this list

this will fail if ʟC has a length of 1, so the program stops. Once the error message is ignored, we can see the output:

# Julia 1.0, 60 bytes

~v=(!(*,a=0)=v[v.|>i->(a=max(a,i))i];v>[] ? [[!<=];~!>] : v)


Try it online!

The helper function ! is called twice at each step of the stalin sort, once with <= for the sorted part and with > for the "rest" part.

the comparison operator (> or <=) takes the place of * in !, including implicit multiplication: (a=max(a,i))i(a=max(a,i))*i(a=max(a,i))>i

## Clojure, 133 bytes

(fn f[i](let[[x y](reduce(fn[[a b]j](if(>(last a)j)[a(conj b j)][(conj a j)b]))[[(first i)][]](rest i))](if(seq y)(cons x(f y))[x])))


I wish this would have been shorter. f` implements the Stalin Sort which is called recursively as deemed necessary. TIO.