# Iteratively sort a list

Given a list of Integers greater than zero, Sort each of the unique values in ascending order, then repeat the process on the remaining duplicate values and append.

Example:

[1,5,2,2,8,3,5,2,9] ==> [1,2,3,5,8,9,2,5,2]
[8,5] ==> [5,8]
[2,2,2] ==> [2,2,2]

• You should add more test inputs, including "corner" cases such as [4 4 4] and [8 5], as well as [] if the empty input need to be handled Commented Dec 12, 2023 at 23:43
• Closely related: Simulate Round Robin Scheduling Commented Dec 13, 2023 at 4:37
• added extra cases Commented Dec 13, 2023 at 15:13
• I read this first as cynically sort a list, and was really curious. Still am, but in a different way.
– Scot
Commented Dec 13, 2023 at 23:16
• @DomHastings yeah, i was just lazy typing this out Commented Dec 22, 2023 at 16:30

import Data.List
concat.transpose.group.sort


Try it online! (has an extra 2 bytes for f=)

# Jelly, 5 bytes

ṢŒgZF


Try it online!

A monadic link taking an unsorted list of integers and returning the list sorted as described.

## Explanation

Ṣ     | Sort
Œg   | Group runs of identical digits together
Z  | Transpose
F | Flatten


# Uiua, 11 bytes

▽≠0.♭⍉⬚0⊕∘.


Try it!

• . duplicate input

• ⬚0⊕∘ group by identity, filling with zeros

• ⍉ transpose

• ♭ deshape

• ▽≠0. keep non-zeros

# Vyxal, 28 bitsv2, 3.5 bytes

sĠ∩f


Try it Online!

Bitstring:

1000100001100101100111101000


Port of the Uiua answer except without the 0 filling because it's not needed here. And they say having a fixed array model is a good thing! :p

## Explained

sĠ∩f­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁣⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌­
s     # ‎⁡Sort the input
Ġ    # ‎⁢Group on consecutive items
∩   # ‎⁣Transpose
f  # ‎⁤and flatten
💎


Created with the help of Luminespire.

# Nekomata + -1, 5 bytes

oOᵐůj


Attempt This Online!

oOᵐůj
o       Sort
O      Find a set partition
ᵐů    such that no part contains duplicates
j   Join


The flag -1 finds only the first solution.

The built-in O (\setPartition) uses the following algorithm (taken from Curry's Combinatorial package), which ensures that the first solution is exactly the one we want:

partition    :: [a] -> [[a]]
partition [] = []
partition (x:xs) = insert x (partition xs)
where insert e [] = [[e]]
insert e (y:ys) = ((e:y):ys) ? (y:insert e ys)


# Jelly, 4 bytes

ĠZFị


A monadic Link that accepts a list and yields the "sorted" list.

Try it online!

### How?

ĠZFị - Link: list A            e.g. [8,8,8,3,7,7,3,3]
Ġ    - Group indices of A by value  [[4,7,8],[5,6],[1,2,3]]
Z   - transpose                    [[4,5,1],[7,6,2],[8,3]]
F  - flatten                      [4,5,1,7,6,2,8,3]
ị - index into A                 [3,7,8,3,7,8,3,8]


# R, 40 bytes

function(x)x[order(ave(!x,x,FUN=seq),x)]


Try it online!

Shorter to use order than split.

# R, 55 bytes

function(x,y=sort(x))unlist(split(y,ave(!y,y,FUN=seq)))


Try it online!

Noticed the split and ave characterization about 2 minutes after posting the longer answer below. Rough R equivalent to the Jelly answer.

# R, 73 bytes

f=function(x,o={},d=duplicated(x))'if'(sum(x),f(x[d],c(o,sort(x[!d]))),o)


Try it online!

Naive implementation: sort unique values and recurse on remainder, appending as you go. Probably there's a shorter way.

import Data.List
f[]=[]
$#2  Attempt This Online! Edit: -4 bytes thanks to Neil, by changing I/O format Input and output are newline-separated decimals. First sort normally, then sort (stably) again using the occurrence index • You could save 4 bytes by taking input on separate lines. Try it online! – Neil Commented Dec 13, 2023 at 8:58 # Ruby, 41 bytes ->l,*r{l.sort_by{|x|[(r<<x).count(x),x]}}  Try it online! # APL (Dyalog Classic), 15 bytes -2 bytes thanks to att. {0~⍨,⍉⊣¨⌸⍵[⍋⍵]}  Try it online! Explanation {0~⍨,⍉⊣¨⌸⍵[⍋⍵]}­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁡⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁣⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁤⁪‏‏​⁡⁠⁡‌⁣​‎⁪⁪⁠⁪⁪⁠⁪⁪⁠⁪⁪⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁣⁢⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏‏​⁡⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏‏​⁡⁠⁡‌⁢⁣​‎‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌⁢⁤​‎‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌⁣⁡​‎‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌­ { } # ‎⁡dfn ⍵[⍋⍵] # ‎⁢sort ⊣¨⌸ # ‎⁢⁢groups into matrix, padding with zeros ⍉ # ‎⁢⁣transpose , # ‎⁢⁤ravel (flatten) 0~⍨ # ‎⁣⁡remove zeros 💎  Created with the help of Luminespire. I think that using a dfn rather than tacit is probably shorter here, since we are applying a bunch of monadic functions, and sorting is no shorter in tacit: ⊂∘⍋⌷⊢. • ⍴⍨∘⍴⌸ -> ⊣¨⌸ – att Commented Dec 13, 2023 at 21:11 • @att Thanks! I was trying to think of a way to "reshape into the shape of" but that is a very interesting solution. – Tbw Commented Dec 14, 2023 at 9:30 # PowerShell Core, 73 bytes $f={param($a)if($a){($g=$a|group).Name
&$f($g|%{,$_.Name*($_.Count-1)})}}


Try it online!

Recursive function
Takes an array as a parameter
Returns an array

### Explanation

param($a) # The array in variable$a
if($a){...} # If the array is empty, do nothing, otherwise: ($g=$a|group).Name # Group the numbers in the array, store the groups in$g and return the unique elements sorted
$g|%{,$_.Name*($_.Count-1)} # From the groups, rebuild a list with one element less for each elements &$f(...)                     # Recursively invoke the function on the rebuilt list


# Brachylog, 5 bytes

oḅz₁c


Try it online!

### Explanation

o        Sort in ascending order
ḅ       Group consecutive elements together
z₁     Zip without cycling
c    Concatenate


# Charcoal, 24 bytes

ＵＭθ⟦№…θκιι⟧Ｗ⁻θυ⊞υ⌊ιＩＥυ⊟ι


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

ＵＭθ⟦№…θκιι⟧


Replace each value with a tuple of its occurrence index and value.

Ｗ⁻θυ⊞υ⌊ι


Sort the tuples into order.

ＩＥυ⊟ι


Output the sorted values.

# 05AB1E, 5 bytes

{γζ˜þ


Try it online.

Explanation:

{      # Sort the (implicit) input-list
γ     # Group it into equal adjacent values
ζ    # Zip/transpose; swapping rows/columns,
# using " " implicitly as filler for unequal length lists
˜   # Flatten this list of lists
þ  # Remove all " " by only keeping integers
# (after which the resulting list is output implicitly)


APL(NARS), 23 chars

{0≥≢⍵:⍬⋄a[⍋a],∇⍵∼⍦a←∪⍵}


use:

  {0≥≢⍵:⍬⋄a[⍋a],∇⍵∼⍦a←∪⍵}1 5 2 2 8 3 5 2 9
┌9─────────────────┐
│ 1 2 3 5 8 9 2 5 2│
└~─────────────────┘


zilde has to be as void set for all the types

# APL+WIN, 30 bytes

Prompts for list of integers:

(,⍉⊃(⌈/¨⍴¨n)↑¨n←n⊂n←m[⍋m←⎕])~0


Try it online! Thanks to Dyalog Classic

# JavaScript (Node.js), 62 bytes

a=>a.map(t=$=>[t[$]=9+t[$]||Array($)+t,$]).sort().map(x=>x[1])  Try it online! # Japt, 5 bytes ü Õcf  Try it ü Õcf :Implicit input of array ü :Group & sort by value Õ :Transpose c :Flatten after f : Filtering (to remove null values)  # Haskell + hgl, 11 bytes cx<tx<sr<bg  Attempt This Online! ## Alternative cx<tx<gr<sr  Attempt This Online! ## Explanation • bg group the input into bags of equal elements • sr sort the bags by value • tx transpose • cx concat ## Reflection There are a couple of ways hgl could be improved I'm seeing here: • There are two options for how to sort the bags in bg • Sort by how many items are in a bag • Sort by how early the earliest item appears Neither of these is really helpful in this case. It might be nice to have a case function to sort by the value in the bags which would save us here, but really we need an option for the user to specify how to sort (wouldn't help here since sr<bg is already quite short). • There's probably an argument to be made to have a combined cx<tx. I can see that being used in more places than just here. # Python, 53 bytes f=lambda L:[*map(L.remove,x:={*L})]and sorted(x)+f(L)  Attempt This Online! Straight-forward method used by many other answers previously: Pick, sort and remove uniques and start over. # Scala 3, 118 bytes A Port of @matteo_c's Haskell answer in Scala. Golfed version. Attempt This Online! _ match{case Nil=>Nil;case x=>x.sorted.distinct++f(x.sorted.groupBy(identity).mapValues(_.tail).values.flatten.toSeq)}  Ungolfed version. Attempt This Online! object Main extends App { def f(lst: List[Int]): List[Int] = lst match { case Nil => Nil case x => val sorted = x.sorted val distinctElements = sorted.distinct val groupedElements = sorted.groupBy(identity).mapValues(_.tail).values.flatten.toList distinctElements ++ f(groupedElements) } val testcases = List( (List(1, 5, 2, 2, 8, 3, 5, 2, 9), List(1, 2, 3, 5, 8, 9, 2, 5, 2)), (List(4, 4, 4), List(4, 4, 4)), (List(8, 5), List(5, 8)), (List[Int](), List[Int]()) ) testcases.foreach { case (input, expectedOutput) => assert(f(input) == expectedOutput, s"Test failed for input:$input")
}

println("All tests passed!")
}


# Desmos, 63 bytes

f(l)=sort(l,[l[1...i][l=l[i]].countfori=[1...l.count]]2l.max+l)


Port of some other answers which sort by running occurrence count and value of the corresponding element.

Try It On Desmos!

Try It On Desmos! - Prettified

Q, 51 Bytes

{\$[x~();x;asc[key g],.z.s x asc(,/)_[1]'[g:(=:)x]]}
`

The above function takes an implicit parameter, x, and:

• returns x if it is empty
• otherwise, groups the items in x using K function =: which is equivalent to Q function group. This yields a dictionary where each key is a unique items in x and each value is a list of the indexes at which the item occurs in x
• and returns:
1. the sorted, unique items in x. The unique items are found by taking the keys of the group dictionary

concatenated with

1. the results of a recursive call to the function (.z.s) with the remaining items as the parameter. The remaining items are found by dropping the first index from each list in the group dictionary values (using _[1]'), merging the lists (using ,/), and grabbing the items at those indices from x