DropSort it like it's hot
Haskell, 67 59 58 bytes
(q:r)!x|x<last q=q:r!x|1<2=(q++[x]):r
_!x=[[x]]
foldl(!)[]
Explanation: Given a list of lists (that are already sorted) and a value x
, the !
operator will place x
at the end of the first list whose last element is less than or equal to x
. If no such list exists, the list [x]
is placed at the end.
Try it online.
Husk, 10 bytes
hUmü<¡Ṡ-ü<
Try it online!
This is a combination of my other Husk answer and xnor's Haskell answer.
The duplicate ü<
feels clunky, but I don't know how to get rid of it...
Explanation
The function ü<
translates to nubBy(>)
in Haskell.
It traverses a list from left to right, keeping those elements for which no previously kept element is strictly greater.
In other words, it performs dropsort.
The leftover elements are obtained by taking list difference of the original list and the result of ü<
.
hUmü<¡Ṡ-ü< Implicit input, say x = [2,3,5,4,4,2,7].
¡ Iterate
Ṡ- list difference between argument
ü< and its dropsort: [[2,3,5,4,4,2,7],[4,4,2],[2],[],[],[],...
m Map
ü< dropsort: [[2,3,5,7],[4,4],[2],[],[],[],...
U Prefix of unique elements: [[2,3,5,7],[4,4],[2],[]]
h Drop last element: [[2,3,5,7],[4,4],[2]]
Haskell, 50 bytes
import Data.List
f[]=[]
f l|r<-nubBy(>)l=r:f(l\\r)
Try it online!