[Question]
  [
**This question already has answers here**:
 
 
[DropSort it like it's hot](/questions/137549/dropsort-it-like-its-hot)
 (24 answers)
 
Closed 2 years ago.
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]
```
## Task
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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so shortest answer (in bytes) per language wins!
  
[Answer]
# [Jelly](https://github.com/DennisMitchell/jellylanguage), 10 bytes
```
¬ª\nx@¬µ∆¨≈ì-∆ù
```
[Try It Online!](https://jht.hyper-neutrino.xyz/tio#WyIiLCLCu1xcbnhAwrXGrMWTLcadIiwiw4fFkuG5mClZIiwiIixbIlsxLCAyXSwgWzIsIDFdLCBbMSwgMiwgNCwgMSwgMl0sIFsxLCAwLCAwLCAxLCAxXSwgWzEsIDIsIDQsIDgsIDQsIDIsIDFdLCBbOCwgNCwgMiwgMSwgMiwgNCwgOF0sIFs3LCAxLCAyLCA4LCA0LCAxMCwgMSwgNCwgMl0iXV0=)
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.
```
[Answer]
# [R](https://www.r-project.org/), ~~58~~ 57 bytes
```
f=function(a,b=a<cummax(a)){any(b)&&f(a[b]);print(a[!b])}
```
[Try it online!](https://tio.run/##lY/RCsIwDEXf9xdOGAn0wY6Bgu5LVEZaVii4TrpWFPHbazt9VFgTAgnk3NzYYHvp7aRvfTc5umjTTaN1bVCt8kY6PRogJlo6SD8MdAdCfJJ5gMCqUkBHccb91WrjYr@Kw@u3IEjgrEYsJDko1ylOpsTi33LN@PLlqMwalqXP2SYmz7@yi5Vl7gt84OXYdkYSzJPPZn6uCG8 "R ‚Äì Try It Online")
Prints the arrays in reverse order.
Add one byte to print in the same order as the example ([try it here](https://tio.run/##lY/bCsIwDIbv9xbOmwR6YcdAQfskU0ZaNiy4DnrwgPjstZteKqwJgRDy/fljo@1UsE5fu9Z5umjTutF6EXvRB6O8Hg0Qk4IOKgwD3YEQn@483oCalTzhXvdA5gESMTVNmrx@K4ICzirEQpGHcj3F0ZRY/FuuGF@@nJRZzbL0Oduk5PlXdqmyzH2BD7wc287IBPPJZz0/V8Q3)):
```
f=function(a,b=a<cummax(a)){show(a[!b]);if(any(b))f(a[b])}
```
[Answer]
# [Haskell](https://www.haskell.org/), ~~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!](https://tio.run/##XYzNagMhFIX3PsUhZDHDGIhDIUFiniBdZWmlGHDG0GQa1DSbefepP@20BETP/c53tdp/mMtlmrrK8lCLXloVpCKdVCI@PbxUTjjzZZw38LyDI32l@anOvhvtTosCwtI1TVwf2X4dkeUZwk1XfR4gcNW313fc7uEY3GGAJKi8/XwgGB9qNA0W/G1YpPDTLLt/XaoIxkx2q7gMyWiraAotZSUwipbihSKFGa3zieHZ2ua7nYu/eTZKsflFxWDlu@Qqpcj0DQ "Haskell ‚Äì Try It Online")
[Answer]
# [Python 3](https://docs.python.org/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!](https://tio.run/##XU/RCsMgDHz3K/KoqxuzG2wIfknwwVFlwmqlOui@vtN23WAQEu4uOXLxle9DOM2zUw/T3zoDSSYwoUNMhzhE6pkbRvB8Ah9wZ8Ozt6PJliamUcq90N7BpFRvJppQ@kboTdCNK1tztiknUIAEBYdWc4ItB1FnxRzOBX2EMo9Lif@N69K3wx/66pW@bMSqi9XovJprQmqSXHLA8pMkAHH0IVNHM2PzGw "Python 3 ‚Äì 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 (`[]`)
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 21 bytes
Anonymous tacit prefix function.
```
{m/‚çµ‚ä£‚éï‚Üê‚çµ/‚ç®~m‚Üê‚çµ‚â†‚åà\‚çµ}‚ç£‚â°
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///vzpX/1Hv1kddix/1TX3UNgHIBvJX1OVC2I86Fzzq6YgBsmof9S5@1LnwfxpYou9RV/Oj3jWPerccWm/8qG0iUHNwkDOQDPHwDP6fpmCoo2DElaZgpKNgyAXh6SiY6MCEgZQBGBmiyVuASaguBAcuDRQ1h/Eh0oYQU0AKAQ "APL (Dyalog Unicode) ‚Äì 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 **m**ask)
‚ÄÉ`~`‚ÄÉ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`
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), 17 bytes
```
{x@.=+(x<|\x*)\1}
```
[Try it online!](https://ngn.bitbucket.io/k#eJxtTkEOwjAMu+8VObZQoSWq1ImAxD9Yr3tDJaBvx2mmiQMX17EdN9v11R6X+zm023ttp7jyZ5q2ZyEmoYUy8QyaSarJEGtPQHAhrj0k0cTRLUtbIAyuwOi5UWaG2AvjZ8P+8Kp91pT1aN1dd5BZ4Gd0W40n/lzaQ4HAs/recUkh04EjAa7A+AVYMTXG)
Collaborative effort from @ngn, @Bubbler and @chrispsn at [the k tree](https://chat.stackexchange.com/rooms/90748/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)](https://codeberg.org/ngn/k), 27 bytes
```
f:{{(,x),f y}/x@&'~:\x=|\x}
```
[Try it online!](https://ngn.bitbucket.io/k#eJxVjsEKAyEMRO9+RU6tQqBVBGVDof+x69VvsGzXb++sWksvg8m8yZiXfddcDGd6HbfyvFzrspXHeyuHUnm1TC5VtuQwOCabqmYnbM0wmTy2jdKgyAvUDLg73XQwHcz/ZGw6Drc8RWEvs2P9ETOTwEZwHm3n0U6GL9IT9t5m39sDRWykN8w/IhIafz4aBU6gRn0AvNs7Ow==)
```
 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
```
[Answer]
# [BQN](https://mlochbaum.github.io/BQN/), 21 20 bytes[SBCS](https://github.com/mlochbaum/BQN/blob/master/commentary/sbcs.bqn)
*-1 byte by omitting `ùïä` in the header for the base case*
```
{‚ü®‚ü©:ùï©;ùïä‚ä∏‚àæ‚üú<¬¥‚åà`‚ä∏=‚ä∏‚äîùï©}
```
[Try it here](https://mlochbaum.github.io/BQN/try.html#code=RuKGkHvin6jin6k68J2VqTvwnZWK4oq44oi+4p+cPMK04oyIYOKKuD3iirjiipTwnZWpfQoK4o2J4omNRsKo4p+oMeKAvzIsIDLigL8xLCAx4oC/MuKAvzTigL8x4oC/MiwgMeKAvzDigL8w4oC/MeKAvzEsIDHigL8y4oC/NOKAvzjigL804oC/MuKAvzEsIDjigL804oC/MuKAvzHigL8y4oC/NOKAvzgsIDfigL8x4oC/MuKAvzjigL804oC/MTDigL8x4oC/NOKAvzLin6kK).
```
{‚ü®‚ü©:ùï©;ùïä‚ä∏‚àæ‚üú<¬¥‚åà`‚ä∏=‚ä∏‚äîùï©} 
 ‚ü®‚ü©:ùï©;               # 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.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jellylanguage), 13 bytes
```
¬ª\=¬π∆ô∆ä·πÑ·πõ¬•/¬µ√êL
```
[Try It Online!](https://jht.hyper-neutrino.xyz/tio#WyIiLCLCu1xcPcK5xpnGiuG5hOG5m8KlL8K1w5BMIiwiIiwiIixbIls3LCAxLCAyLCA4LCA0LCAxMCwgMSwgNCwgMl0iXV0=)
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
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 26 bytes
```
Ôº∑Œ∏¬´‚âî‚ü¶‚üßœÖ‚âîŒ¶Œ∏‚à®‚àßœÖ‚ÄπŒ∫‚åàœÖ¬¨‚äûÔºØœÖŒ∫Œ∏Ôº©‚ü¶œÖ
```
[Try it online!](https://tio.run/##PYw9C8JAEERr/RVb7sIKGgQFqyBYqUl/XHHEwxy5JOY@VBB/@5mksHtvZpiqVq7qlU3pVRurAQeCz3KRe2/uHQrJEOnw95OxQTscGAqHeXfDyHDW3mPDcFFv08YWIxExXPuAZfR18dBOhd5Ny4bmapgOS2e6gEflA4ooaYy@KQmxY9gwZAx7hu3I69lHyqRMq6f9AQ "Charcoal ‚Äì 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.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 51 bytes
```
f=->a,*b{a[c=0]&&f[a.map{|i|i<c ?i:b<<c=i}-[p(b)]]}
```
[Try it online!](https://tio.run/##KypNqvz/P81W1y5RRyupOjE62dYgVk0tLTpRLzexoLomsybTJlnBPtMqycYm2TazVje6QCNJMza29n90tKGOglGsDpcCmKGjYKKjgCxiAEZAhiGqGgswaQQTR3DhCsDi5jARiAJDiFkgpbFcsXqpickZ1TWJNQpAh8ZaKxSUlhTX/gcA "Ruby ‚Äì 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
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 99 bytes
```
f=If[#=={},{},Join[{#},f@#2]&@@Fold[Insert[#,#2,{If[#2<#[[1,-1]],2,1],-1}]&,{#[[{1}]],{}},Rest@#]]&
```
[Try it online!](https://tio.run/##PY1NC8IwDIZ/TGAHiWiLoKCDnoR5Eq8lh6ErDtwGW2@hv72@20RowpMnH@3q@G66OrbPOudQVsFTWWpivNvQ9l4pcXBkpXDuOnxevuqnZoyemCzrPG4v5L3hrRFhy0ZASQpWWAUJTiV@NFN0JFLk@9j20W3CzqkatvgJS8hgPvDfzLTw6k@Ide5Hq0V9XHi2Zg9EM6Vz/gI "Wolfram Language (Mathematica) ‚Äì 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
      ]]&
```
[Answer]
# [C (clang)](http://clang.llvm.org/), ~~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!](https://tio.run/##hVfbbqMwEH3vV1hIlYCAtvhCu6VpH1b7FUlUJYR0kzi0CpE22iq/vlkDBsb20I1aiD3jmTnn@JY8zuWyfLte99khC/MsXGUbP1xGMvjcvB/9bD@VWVB/O0xDP5@upssg28dxNpmsgnD1dHgJ88lkGq4eP47b8rTxvXl5uybexF89L4NIDVpFcSyD7HJVZnJYbks/IJ83RH3qjlNRnV6T2YJMyWcSEXrJhm7adtOIJLCb9d53zV9i2fkQLSI8Ig/N044iWq/B2LtDr7T1uu/srXvSZuVNvQYU2fpX2z/F@8ZvwQXfdDPU7YhAO7Xs1LIzy84sO7fs3LILyy4se2rZ02DAFDagqhZUW32ktdFvpt9cv4V@p4CY4vxR5Kdi/Zq83tlKh8Da2qC3lmLoMvmFrgMKoxcrg3ZlUDs@7aeiUx21qlNBImOgE2ukVorWWvf2usCwqG@C4mKAXrAogF2jq9eNA5BZAJkBkLkA2QhAhgJkKECGAmQjADmcP8ZiBS4aI3ctdER13m8pDincIoUbpPB6OcAERos5eUYI4yhhHCWMo4RxuKvAglBfivoy1JehQohOiAdEAtFLoCRyjcOuTl3jqBDCEkIYQghDCGEIIVwhxIgQAhVCoEIIVAiBCiFQIQQqhECFECNCpJ0Q983ZlDg7ZgoP12bJcNeFfrErpxbxqUF8ahCvIjnBR6hOUapTlOoUpTpFqU5RqutecKoN8OwjB27pcPeDCxvOLQge0accOa6wwwrb/rHNH9tFsT0UW@TYEsfmIDYDMbIxqo3rQ9ctbaIlZBo2GGxw2BCwkUqdJv@1PIbqWeT74thm8ebnn3R@/v5D/QsvIrDNPD1OXWmJX2u1LdfFWQ27y/TXJxunizLIyGTSeHd32U55qSK1F8HGvMigVV2ntLlyzN31eeYFQ@dQpC5QFSeb3DAvHH5b3a4V5O1LjfvRU8/TbLsAIS9OxgWJn42k/ikiMnBLm5cd/sd5CUfoNVWpIvuFhcAnJXAocYKkBD4uiRghJUpI82tDOUkVBAQYZmadp3JsfYJdm2CnEhzqBDs7gcG6@sWjJudsB5k22TaJ9L5UJP7vZ4hwublc/@YbuXyrrvHvfw "C (clang) ‚Äì Try It Online")
*Saved 2 bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/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.
[Answer]
# Haskell, 50 bytes
```
import Data.List
f[]=[]
f x|n<-nubBy(>)x=n:f(x\\n)
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/PzO3IL@oRMElsSRRzyezuIQrLTrWNjqWK02hoibPRjevNMmpUsNOs8I2zypNoyImJk/zf25iZp5tQVFmXolKWrS5joKhjoKRjoKFjoIJkG0A5puAhAwNYv8DAA "Haskell ‚Äì Try It Online")
I took the brilliant idea of using `nubBy(>)` to perform a single "Stalin sort" from [HPWiz on anagol](http://golf.shinh.org/reveal.rb?Stalin+Sort+2/HPWiz_1606561165&hs).
[Answer]
# 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!](https://tio.run/##dY3RCoMgFIbv9xTuTpnJjGAjsB5EvDg23RqRUc3Xdy1Zg2E3B87/fT//EzxMzdgOc9a7mwnBChAVnKCWwGzbzWbEfgkqXx81G17TA3tSgvBUC6kIZYxZrIkqITSun1xnWOfu2GLJKcoVIYe/OKeIJ@KPTVGxwP1ahGm@9a/r3Vn5wU1PWJcvjzo/r38Rh8Mb "JavaScript (Node.js) ‚Äì 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
```
[Answer]
# TI-Basic, 80 [bytes](https://codegolf.meta.stackexchange.com/a/4764/98541)
```
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`](https://codegolf.meta.stackexchange.com/a/8580/98541) 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](https://codegolf.meta.stackexchange.com/q/4780/98541) is ignored, we can see the output:
[![enter image description here](https://i.stack.imgur.com/Vrh3t.jpg)](https://i.stack.imgur.com/Vrh3t.jpg)
[![enter image description here](https://i.stack.imgur.com/CPp9d.jpg)](https://i.stack.imgur.com/CPp9d.jpg)
[Answer]
# [Julia 1.0](http://julialang.org/), 60 bytes
```
~v=(!(*,a=0)=v[v.|>i->(a=max(a,i))i];v>[] ? [[!<=];~!>] : v)
```
[Try it online!](https://tio.run/##XYzfqsIwDIfvfYrsLj1UcSJ4UDufwCcovQisQg61jq0WBdmrz7r6h2Mukny/j@Tv7JjKyzD0UWGBP5LUXKio4@xW8bRCUke6IEkWgs0mVtrADrQutsps@qIysIYohsOpBQb20FqqHXvboZhAqgAKbCSHexto1lDbWUyvRte07IPzGDLW3DWOrtiH//qbrK8HXUpYmIleSCjTeJCEZYJPnCHz2/@O/Xn1gbdO6erFWZfzkZf5UZKr0TwWcwc "Julia 1.0 ‚Äì 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`
[Answer]
## 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](https://tio.run/##JY5LCoRADET3nqKWCbgYRVAYmIuELFrthm5EZ/yAnt6JuntJfahumNI2@/Ok3gcEUBgRJCoNfhXZcSjNvt86b4KIQ6tJKQb60OCWFY4Ti6NuGhNaJFZ52Bm3yixCIc5mjCbp1XUz3x2L/@HgK7Bgp2DMsluIOcvoO8dxHUYbBKlzFDnKHE2Oyvh130alubM3SGo09lZIgRIVqoeUz/MP).
]