Sever-sort an array

Challenge

Given a non-empty array of integers, e.g.:

[5, 2, 7, 6, 4, 1, 3]


First sever it into arrays where no item is larger than the previous (i.e. non-ascending arrays):

[5, 2] [7, 6, 4, 1] [3]


Next, reverse each array:

[2, 5] [1, 4, 6, 7] [3]


Finally, concatenate them all together:

[2, 5, 1, 4, 6, 7, 3]


This should be what your program outputs/function returns. Repeat this procedure enough times and the array will be fully sorted.

Rules

• Input and output may be given through any standard methods, and may be in any reasonable array format.
• The input array will never be empty, but may contain negatives and/or duplicates.
• The absolute value of each integer will always be less than 231.

Test cases

Hopefully these cover all edge cases:

[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]


Scoring

This is , so the shortest code in bytes wins.

• What's the big-o of this sorting method? Dec 21, 2016 at 22:08
• @mbomb007 I don't understand big-o notation very well, but I think a single iteration is O(n). Multiply that by worst-case n iterations and you get O(n^2) (worst-case; best-case would be O(n), I think, for a single iteration). Dec 21, 2016 at 22:23
• That sounds right to me, however it's worth pointing out that reversing an array isn't a very efficient operation, so it's a slow O(n^2) Dec 21, 2016 at 22:45
• @WheatWizard reversing an array doesn't require room for a copy of the array, only room for a single element. and is O(n). swap first and last elements then swap second and second last elements etc, when you get to the middle stop. Dec 22, 2016 at 11:27
• Reversing is O(n), but reversing can be built right into the algorithm (that's what my JS answer does); since each iteration loops over each item in the array once, a single iteration is O(n). (I think...) Dec 22, 2016 at 14:27

JavaScript (ES6), 64 bytes

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q


Recursion FTW! The basic algorithm in use here is to keep track of the current non-ascending run in an array, "returning" it whenever an ascending element is found. We do this recursively, continually concatenating the results, until we run out of items. By creating each run in reverse ([n,...z] instead of [...z,n]), we can avoid the lengthy .reverse() at no cost.

Test snippet

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

g=a=>console.log("Input:",[${a}],"Output:",[${f(a)}])

g([1])
g([1,1])
g([1,2])
g([2,1])
g([3,2,1])
g([3,1,2])
g([3,1,1,2])
g([5,2,7,6,4,1,3])
<input id=I value="5, 2, 7, 6, 4, 1, 3">
<button onclick="g((I.value.match(/\d+/g)||[]).map(Number))">Run</button>

• Can you explain how your array gets parsed into your first parameter [n,...a]. What is n? Is that just the first item in your array? Dec 22, 2016 at 0:05
• @obarakon Correct. n is the first item in the array, and a is the rest of the array. You can find more info here. Dec 22, 2016 at 0:12
• Thank you. That was very helpful. Since your first parameter is an array, why do you need to include the ...a? Is that just so you can take advantage of n? One more thing, when you call f(a,q), does q get set to the parameter z? Dec 22, 2016 at 0:21
• @obarakon Well, f=([n])=>... would only capture the first element, and f=([n,a])=>... would capture only the first in n and the second in a. Another way to do what f=([n,...a])=>,,, does would be f=a=>(n=a.unshift(),.... Dec 22, 2016 at 4:49
• And since z is the second parameter in the function, when f(a,q) is called, f sees it as z. Hope this helps! Dec 22, 2016 at 4:50

Python 3, 63 bytes

f=lambda x,*p:x[:1]>p>()and p+f(x)or x and f(x[1:],x[0],*p)or p


Try it online!

Jelly, 8 bytes

Ṁ;<œṗ³UF


Try it online!

Explanation:

Ṁ;         Prepend the list [a1, a2… an] with its maximum.
<        Elementwise compare this with the original list:
[max(a) < a1, a1 < a2, …, a(n-1) < an, an]
The first element is always 0.
œṗ³     Partition the original list (³) at the indices
of the non-zero values in the working list.
(The spurious an at the end of the left argument,
resulting from comparing lists of different sizes,
is ignored by this operation, thankfully.)
U    Reverse each part.
F   Flatten.

• I was on the verge of hitting Save Edits when I saw your answer... Well done. Dec 22, 2016 at 0:09
• @Dennis Heh, so you added Dyalog partitioned enclose, but what about APL2 partition?
Dec 22, 2016 at 9:09

JavaScript (ES6), 70 bytes

Sure, this is already beaten by ETHproductions answer, but that's the best I could come up with so far without using recursion.

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x


Note: Initializing both r and o to the exact same object with r = o = [] may look like a hazardous idea. But it is safe to do so here because r is immediately assigned its own instance (containing the first element of a) on the first iteration with r = [n, ...r].

Test cases

let f =

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

console.log(JSON.stringify(f([1])));
console.log(JSON.stringify(f([1, 1])));
console.log(JSON.stringify(f([1, 2])));
console.log(JSON.stringify(f([2, 1])));
console.log(JSON.stringify(f([2, 3, 1])));
console.log(JSON.stringify(f([2, 1, 3])));
console.log(JSON.stringify(f([2, 1, 2])));
console.log(JSON.stringify(f([2, 1, 1])));
console.log(JSON.stringify(f([3, 1, 1, 2])));
console.log(JSON.stringify(f([3, 2, 1, 2])));
console.log(JSON.stringify(f([3, 1, 2, 2])));
console.log(JSON.stringify(f([1, 3, 2, 2])));
console.log(JSON.stringify(f([1, 0, 5, -234])));
console.log(JSON.stringify(f([1, 0, 1, 0, 1])));
console.log(JSON.stringify(f([1, 2, 3, 4, 5])));
console.log(JSON.stringify(f([5, 4, 3, 2, 1])));
console.log(JSON.stringify(f([2, 1, 5, 4, 3])));
console.log(JSON.stringify(f([2, 3, 1, 5, 4])));
console.log(JSON.stringify(f([5, 1, 4, 2, 3])));
console.log(JSON.stringify(f([5, 2, 7, 6, 4, 1, 3])));
console.log(JSON.stringify(f([-5, -2, -7, -6, -4, -1, -3])));
console.log(JSON.stringify(f([14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9])));

• No worries, I love seeing different approaches. And one often ends up becoming shorter than another after golfing :-) Dec 21, 2016 at 23:17

MATL, 15 bytes

lidO>vYsGhXSOZ)


Input is a column vector, with the format [5; 2; 7; 6; 4; 1; 3] (semicolon is the row separator).

Try it online!

Take input [5; 2; 7; 6; 4; 1; 3] as an example.

Explanation

l     % Push 1
% STACK: 1
i     % Push input
% STACK: 1, [5; 2; 7; 6; 4; 1; 3]
d     % Consecutive differences
% STACK: 1, [-3; 5; -1; -2; -3; 2]
O>    % Test if greater than 0, element-wise
% STACK: 1, [0; 1; 0; 0; 0; 1]
v     % Concatenate vertically
% STACK: [1; 0; 1; 0; 0; 0; 1]
Ys    % Cumulative sum
% STACK: [1; 1; 2; 2; 2; 2; 3]
G     % Push input again
% STACK: [1; 1; 2; 2; 2; 2; 3], [5; 2; 7; 6; 4; 1; 3]
h     % Concatenate horizontally
% STACK: [1 5; 1 2; 2 7; 2 6; 2 4; 2 1; 3 3]
XS    % Sort rows in lexicographical order
% STACK: [1 2; 1 5; 2 1; 2 4; 2 6; 2 7; 3 3]
OZ)   % Get last column. Implicitly display
% STACK: [2; 5; 1; 4; 6; 7; 3]

• I translated your answer to Octave saved me 31 bytes! Dec 23, 2016 at 4:47

Mathematica, 30 27 bytes

3 bytes saved due to @Martin Ender.

Join@@Sort/@Split[#,#>#2&]&


Anonymous function. Takes a list of numbers as input and returns a list of numbers as output.

• Beat me to it! :) Dec 22, 2016 at 18:55

05AB1E, 191816 14 bytes

Saved 2 bytes using Luis Mendo's sorting trick

ü‹X¸ì.pO¹)ø{ø¤


Try it online!

Explanation

Example input [5, 2, 7, 6, 4, 1, 3]

ü‹               # pair-wise less-than
# STACK: [0, 1, 0, 0, 0, 1]
X¸ì            # prepend a 1
# STACK: [1, 0, 1, 0, 0, 0, 1]
.p          # prefixes
O         # sum
# STACK: [1, 1, 2, 2, 2, 2, 3]
¹        # push input
# STACK: [1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]
)       # wrap stack in list
# STACK: [[1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]]
ø      # zip
# STACK: [[1, 5], [1, 2], [2, 7], [2, 6], [2, 4], [2, 1], [3, 3]]
{     # sort
# STACK: [[1, 2], [1, 5], [2, 1], [2, 4], [2, 6], [2, 7], [3, 3]]
ø    # zip
# STACK: [[1, 1, 2, 2, 2, 2, 3], [2, 5, 1, 4, 6, 7, 3]]
¤   # tail
# OUTPUT: [2, 5, 1, 4, 6, 7, 3]


Previous 16 byte solution

Dü‹X¸ì.pO.¡€g£í˜

• Those linebreaks explained it wonderfully... :-P Dec 21, 2016 at 23:09
• @StewieGriffin: Yeah, I changed up the code and posted before I had rewritten the explanation :P Dec 21, 2016 at 23:10
• I know this is 7 years old, but for anyone else coming across this, it can be 9 bytes now using the same approach: ü‹.¥øí{øθ. Jan 29 at 13:00

Python 2, 100 bytes

A really terrible golf, but I wanted to post my solution (one does not simply outgolf Dennis)...

d=input();L=[];x=0;d+=-~d[-1],
for i in range(1,len(d)):
if d[i]>d[i-1]:L+=d[x:i][::-1];x=i
print L


Test on repl.it!

Input should be given as a Python list literal, such as [5, 3, 4, 2, 6, 1].

The basic idea is to make heavy use of Python's slicing syntax, slicing each necessary section from the array, reversing it, and adding it to the new array.

• I think the first line can be d,L,x=input(),[],0;d+=.... Dec 22, 2016 at 6:16
• @Dopapp that's exactly the same byte count Dec 22, 2016 at 6:51

Pyke, 11 8 bytes (old version)

$0m<fm_s  Try it here! (works on latest version) $        -     delta(input)
0m<     -    map(i<0 for i in ^)
f    -   split_at(input, ^)
m_  -  map(reverse, ^)
s - sum(^)


Retina, 163 bytes

Yes, I know how horrid this is. Supporting zeros and negatives was super fun. Byte count assumes ISO 8859-1 encoding.

\d+
$* (?<=-1*)1 x - x,1 x¶1 \b(1+),(1+\1)\b$1¶$2 ,,1 ,¶1 x,(¶|$)
x¶¶
(?<=\b\1x+(?=,(x+))),\b
¶
O%$#.(?=(.*))$.1
+¶
,
\bx
-x
(\w+)
$.1 ^, 0, ,$
,0
,,
,0,
^$0  Try it online Explanation: \d+ # Convert to unary$*
(?<=-1*)1                   # Replace negatives with x's instead of 1's
x
-                           # Remove minus sign

x,1                         # Separate if negative before positive
x¶1
\b(1+),(1+\1)\b             # or greater positive follows a positive
$1¶$2
,,1                         # or positive follows a zero
,¶1
x,(¶|$) # or zero follows a negative x¶¶ (?<=\b\1x+(?=,(x+))),\b # or negative follows a negative of greater magnitude. ¶ O%$#.(?=(.*))              # Swear at the input, then reverse each line
$.1 +¶ # Remove breaks, putting commas back , \bx # Put the minus signs back -x (\w+) # Replace unary with length of match (decimal)$.1
^,                          # Do a bunch of replacements to resurrect lost zeros
0,
,$,0 ,, ,0, ^$
0


JavaScript (ECMA 6), 121128125119 108 bytes

f=a=>{p=a[0],c=[],b=[];for(e of a){e>p&&b.push(c.reverse(c=[]));c.push(p=e)}return[].concat.call([],...b,c)}


Lambda expression takes a single Array parameter, a.

Thanks to @ETHproductions for helping me see my first mistake.

• Nice! I think you can do return(b+","+c).split,  to save a few bytes at the end. Dec 21, 2016 at 23:27
• Better yet, you can use c.unshift instead of c.push to remove the need to reverse c. After doing this, I got 94 bytes. Dec 21, 2016 at 23:31

Ruby, 60 55 bytes

s=->x{x.slice_when{|p,q|p<q}.map{|z|z.reverse}.flatten}


Pretty much what the challenge asked for. I defined a lambda s, that takes an array x, and sever (slices) it into smaller pieces where the following element would be greater than. This gives back an enumerator, which we can call map on and reverse the order of the pieces, before finally bringing it all together with flatten, which concatenates the elements in the defined order into one array.

Tests

p s[[1]]===[1]
p s[[1, 1]]===[1, 1]
p s[[1, 2]]===[1, 2]
p s[[2, 1]]===[1, 2]
p s[[2, 3, 1]]===[2, 1, 3]
p s[[2, 1, 3]]===[1, 2, 3]
p s[[2, 1, 2]]===[1, 2, 2]
p s[[2, 1, 1]]===[1, 1, 2]
p s[[3, 1, 1, 2]]===[1, 1, 3, 2]
p s[[3, 2, 1, 2]]===[1, 2, 3, 2]
p s[[3, 1, 2, 2]]===[1, 3, 2, 2]
p s[[1, 3, 2, 2]]===[1, 2, 2, 3]
p s[[1, 0, 5, -234]]===[0, 1, -234, 5]
p s[[1, 0, 1, 0, 1]]===[0, 1, 0, 1, 1]
p s[[1, 2, 3, 4, 5]]===[1, 2, 3, 4, 5]
p s[[5, 4, 3, 2, 1]]===[1, 2, 3, 4, 5]
p s[[2, 1, 5, 4, 3]]===[1, 2, 3, 4, 5]
p s[[2, 3, 1, 5, 4]]===[2, 1, 3, 4, 5]
p s[[5, 1, 4, 2, 3]]===[1, 5, 2, 4, 3]
p s[[5, 2, 7, 6, 4, 1, 3]]===[2, 5, 1, 4, 6, 7, 3]
p s[[-5, -2, -7, -6, -4, -1, -3]]===[-5, -7, -2, -6, -4, -3, -1]
p s[[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9]]===[3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

• Welcome, nice <s>first</s> second answer, check this: codegolf.stackexchange.com/questions/363/…
– G B
Dec 22, 2016 at 8:40
• Thanks a lot. Turned this into a lambda, as suggested in the link you provided, and saved 5 bytes that way. Dec 22, 2016 at 16:05

Brachylog, 10 bytes

~c:{>=r}ac


Try it online!

Explanation

~c            Deconcatenate the Input
:{>=r}a     Each resulting sublist must be non-increasing, and then reverse it
c    Concatenate

• Does Brachylog's c, when run in reverse, necessarily try splits into fewer lists first?
– user62131
Dec 25, 2016 at 3:26
• @ais523 yes, it does. Dec 25, 2016 at 13:07

Husk, 4 bytes

ṁ↔ġ≤


Try it online!

I've ġot ṁyself the right tools for this job.

Explanation

ġ is "groupby": it divides a list into sublists where in each sublist the given function returns a truthy value for any pair of elements. Used with ≤, this divides the list into non-increasing sequences.

ṁ is "concatmap": it maps a function to each element of a list, and concatenates the results together. With ↔ (reverse), this performs the reverse-and-concatenate final part of the algorithm.

Dyalog APL, 7 15 bytes

Requires ⎕ML←3, which is default on many systems.*

{∊⌽¨⍵⊂⍨1+⍵-⌊/⍵}


∊ enlist (flatten)

⌽¨ each-reversed

⍵⊂⍨ the argument partitioned* by cutting where each corresponding element is larger than its predecessor in

1+ one plus

⍵- the argument minus

⌊/⍵ the smallest element of the argument

Old 7 byte solution fails with non-positive integers:

Requires ⎕ML←3, which is default on many systems.*

∊⌽¨⊆⍨⎕


∊ enlist (flatten) the

⌽¨ each-reversed

⊂⍨ self-partitioned*

* Partition (⊂) is a function which cuts its right argument where the corresponding left argument is larger than the preceding one. (Unfortunately it only accepts non-negative integers, and zero has special meaning.) From version 16, this functionality of ⊂ is available on all systems (even those where ⎕ML≠3), using the glyph ⊆.

Jelly, 6 bytes

$- To A: Ɲ - For each overlapping pair of elements [a, b] in A: < - Is a < b? k - Partition A at the truthy elements U - Reverse each subarray F - Flatten  Haskell, 49 bytes (a:b)%l|any(<a)l=l++b%[a]|1<2=b%(a:l) _%l=l (%[])  Usage example: (%[]) [5,2,7,6,4,1,3] -> [2,5,1,4,6,7,3]. Recursive approach. The function % takes the input list as its first parameter and an accumulator l which keeps track of the non-ascending chunk so far (in reverse order). The base case is reached when the input list is empty and then the result is the accumulator. If the input list is not empty and the first element a doesn't fit in the current chunk (any(<a)l), return the accumulator and append a recursive call on the rest of the list and a as the new accumulator (l++b%[a]). Else, make a recursive call on the rest of the list and a prepended to tha accumulator (b%(a:l)). The main function (%[]) calls % with an empty accumulator. Retina, 98 bytes Byte count assumes ISO 8859-1 encoding. $

-(\d+)
$1$*-/
\d+
$* S-(?<=(-+)/ )(?!\1)|(?=\b(1+))(?<!\2 ) O%\S* ¶ ((-)|1)*/?$2$#1$



Try it online!

R, 64 bytes

cat(unlist(lapply(split(x<-scan(),cumsum(c(F,diff(x)>0))),rev)))


Reads input from stdin. We split the input into a list of vectors using split() which requires a factor variable that groups the input. The factor is created by taking the cumulative sum of the the logical vector for which the difference is positive.

Consider the vector:

x=c(5, 2, 7, 6, 4, 1, 3)


Now taking the difference and prepending F by running y=c(F,diff(x)>0) would produce the following logical vector:

[1] FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE


Taking the cumulative sum cumsum(y) produces a vector where each group is represented by a unique factor upon which we can combine with the split function:

[1] 0 0 1 1 1 1 2

• 60 bytes using diffinv rather than cumsum. Nov 20, 2018 at 21:57

Octave, 75 44 bytes

Based on MATL answer of @LuisMendo

@(a)sortrows([cumsum([1;diff(a)>0]),a])(:,2)


Try it Online!

@(a)[fliplr(mat2cell(f=fliplr(a),1,diff(find([1,diff(f)<0,numel(a)])))){:}]


Try it Online!

reverse the array

f=fliplr(a)


take first difference of f

d = diff(f);


find position of where the next element is less than the previous element

p=find([1,diff(f)<0,numel(a)])


first difference of the positions returns length of each sub array

len=diff(p)


use length of each sub array in mat2cell to split the array to nested list of arrays

nest = mat2cell(f,1,len);


reverse the nested list

rev_nest = fliplr(nest)


flatten the nested list

[rev_nest{:}]


R, 41 bytes

ave(x,diffinv(diff(x<-scan())>0),FUN=rev)


Try it online!

Husk, 12 bytes

Completely and utterly outgolfed by Leo while I was typing in my answer...!

ṁ↔CẊ-Θ:W<¹L¹


Try it online!

ṁ              # map this function:
↔             # reverse
# across all the elements of:
C            # cut the input into sublists given by
Ẋ-          # differences between elements of
W<¹     # list of indices of the input that are less than their successor
Θ:   L¹   # prepended with zero and appended with the length of the input

• Let me introduce you to ġroupby :) codegolf.stackexchange.com/a/218911/62393
– Leo
Feb 11, 2021 at 23:01
• @Leo - I pressed 'submit', only to find your answer staring back at me! Feb 11, 2021 at 23:04

Vyxal 3, 6 bytes

ᵃ>ṁƒVf


Try it Online!

a weird quirk of "partition after truthy indices" means it matches lengths so it will never include the last value when getting booleans from comparing the overlapping pairs. By appending the reversed list we can always have a partition such that the last values are kept

K (ngn/k), 17 15 bytes

{,/|'x@=+\>':x}


Try it online!

Chunks the input on indices where the value is greater than the previous value, reversing each chunk and concatenating back into a single array.

• >':x check whether each element is larger than the prior element
• =+\ group the cumulative sum of this; elements in each run of equal or decreasing values get assigned their own index in the resulting dictionary
• x@ index back into the original input to retrieve the original values
• |' reverse each chunk
• ,/ flatten the chunks back into a single array

Pyth - 15 bytes

s_McQf<@QtT@QTU


Perl 6, 59 bytes

{map |+«*.[0].reverse,m/:s([(\-?\d+)<?{[>=] $0}>] +)+/[0]}  Regex-based solution. Because this is Sparta Perl!! • m/ /: Stringify the input array, and match a regex against it. • (\-? \d+): Match a number, and capture it as $0.
• <?{ [>=] $0 }>: Zero-width assertion that only matches if all $0 captured so far in the current sub-match are in non-ascending order.
• ([ ] +)+: Repeat the last two steps as often as possible, otherwise start a new sub-match.
• map , [0]: Iterate over the sub-matches.
• |+«*.[0].reverse: For each one, take the list of values matched by $0, reverse it, coerce the values to numbers (+«), and slip them into the outer list (|). Perl 6, 63 bytes sub f(\a){flat$_,f a[+$_..*]with first {[<=]$_},:end,[\R,] a}


Recursive list processing solution.
More laborious than I had hoped.
Even though the language has lots of convenient built-ins, there seem to be none for list partitioning (e.g. like Ruby's slice_when or Haskell's takeWhile).

Stacked, noncompeting, 34 bytes

Still constantly developing this language.

{e.b:e b last<}chunkby$revmap flat  Argument lies on TOS. Try it here! chunkby takes a function and collects arrays of contiguous data that satisfy the function. The function then is: {e.b:e b last<} {e.b: } function with arguments [e, <unused>, b]--the element, <the index>, and the chunk being built e < check if e is less than b last the last element of b  This gives a strictly decreasing array. $revmap is basically [rev]map and reverses each item.

flat finally flattens the array.

Some fun for actually sorting the array:

[{e.b:e b last<}chunkby$revmap flat] @:sortstep [$sortstep periodloop] @:sort

10:> @arr
arr out
arr shuf @arr
arr out
arr sort out


This outputs (for example):

(0 1 2 3 4 5 6 7 8 9)
(4 5 1 0 6 7 2 8 9 3)
(0 1 2 3 4 5 6 7 8 9)


Python, 151 139 Bytes

Saved 12 Bytes thanks to @Flp.Tkc!

Nowhere near @Flp.Tkc, let alone...

def s(l):
r=[];i=j=0
while j<len(l)-1:
if l[j+1]>l[j]:r+=l[i:j+1][::-1],;i=j+1
j+=1
r+=l[i:j+1][::-1],;return[i for s in r for i in s]

• Instead of using append, use += data, the trailing comma implicitly constructs a tuple, which is then concatenated with the list, adding the data as the last element in the list. In this context, do r+=l[i:j+1][::-1], Dec 22, 2016 at 16:22

Python 2, 74 bytes

b=[];c=[];a+=9e9,
for i in a[:-1]:
b=[a.pop(0)]+b
if b[0]<a[0]:c+=b;b=[]


Input in a, output in c

Python 3, 191 Bytes

a=[int(i)for i in input().split()]
while a!=sorted(a):
b=[[]]
for i,j in enumerate(a):
if a[i-1]<j:b+=[[j]]
else:b[-1]+=[j]
a=[]
for l in[k[::-1]for k in b]:a+=[k for k in l]
print(a)


I'm not sure if using the sorted function to check is allowed here, but I couldn't think of a good reason against it, and it brought down my byte count by ~30 Bytes.