# Sort every dimension

Given a multidimensional, rectangular array of nonnegative integers, sort it at every depth (lexicographically), starting from the innermost.

For example, with this array:

[ [ [5, 1, 4],
[10, 7, 21] ],
[ [9, 20, 2],
[4, 2, 19] ] ]


You'd sort at the deepest first:

[ [ [1, 4, 5],
[7, 10, 21] ],
[ [2, 9, 20],
[2, 4, 19] ] ]


Then sort at the next depth, lexicographically:

[ [ [1, 4, 5],
[7, 10, 21] ],
[ [2, 4, 19],
[2, 9, 20] ] ]


lexicographic comparison of arrays means comparing the first element, and if they're equal comparing the second, and so on all the way down the line. Here we see that [2, 4, 19] is less than [2, 9, 20] because although the first elements are equal (2) the second aren't - 4 < 9.

Finally, sort at the top depth (lexicographically):

[ [ [1, 4, 5],
[7, 10, 21] ],
[ [2, 4, 19],
[2, 9, 20] ] ]


The first one is less than the second, because [1, 4, 5] is less than [2, 4, 19] because 1 is less than 2.

You may take the lengths of dimensions and/or depth of the array as well.

## Testcases

[2, 1] -> [1, 2]
[[[10, 5, 9], [6, 4, 4]], [[2, 6, 3], [3, 3, 2]], [[3, 8, 6], [1, 5, 6]]] -> [[[1, 5, 6], [3, 6, 8]], [[2, 3, 3], [2, 3, 6]], [[4, 4, 6], [5, 9, 10]]]
[[[6, 9], [12, 17]], [[9, 6], [9, 8]]] -> [[[6, 9], [8, 9]], [[6, 9], [12, 17]]]
[[[9, 1], [2, 5]], [[8, 5], [3, 5]]] -> [[[1, 9], [2, 5]], [[3, 5], [5, 8]]]

• This is gonna sound weird, but can I assume the integers are smaller than 0x10ffff? Jan 23, 2022 at 22:05
Jan 23, 2022 at 22:06
• Can we assume the numbers are a single digit? Jul 12, 2022 at 20:33
• @Seggan nope. (filler) Jul 12, 2022 at 20:35

# Python 2, 30 bytes (@SurculoseSputum)

def f(L):L>f<map(f,L)<L.sort()

Attempt This Online!

#### Old Python 2, 32 bytes (@ovs)

f=lambda s:s>f<s.sort(key=f)or s

Attempt This Online!

#### Old Python 2, 33 bytes (@ovs)

f=lambda s:s>[]<s.sort(key=f)or s

Attempt This Online!

#### Old Python 2, 34 bytes

f=lambda s:s>=[]<s.sort(key=f)or s

Attempt This Online!

This works by side-effect (of in-place sort). It uses comparison to [] as a type check and chained comparison to short circuit (in-place sort returns None, so the chained comparison will always fail)

• @ovs thanks! Re your first point: I think we still need to return s otherwise sort will be asked to sort a bunch of Nones if there is any nesting. Or am I missing something? Jan 23, 2022 at 22:43
• For the comparison you can use the function f itself, which according to Python 2 weird ordering is more than any integer but less than a list. Regarding the output method I missed that you used the return values for sorting, my initial idea for solving this problem was using map to recurse and sorting afterwards, where you get away with returning None.
– ovs
Jan 23, 2022 at 23:06
• @solid.py It rearranges the original list in such a way that if you were to apply map(f,_) afterwards you would get a sorted list, Jan 24, 2022 at 11:04
• @solid.py I'm not 100% sure how this is actually implemented, but I'm fairly confident the following is a valid mental model: The key function, f say, is applied to each element of the sort argument l. The transformed list is then argsorted and the resulting order applied to the original list; one way to think of it is to form triples (f(l[0]),0,l[0]), f(l[1]),1,l[1]),...), sort them and then return the last elements of the sorted triples. - the present case is special in that we ultimately do not want the original elements but the transformed ones. ... Jan 24, 2022 at 16:40
• @solid.py To enforce this behaviour we let f act in-place. However, we also need f to return the updated values because as we just learned sort sorts based on the values returned by f. Jan 24, 2022 at 16:45

# Jelly, 6 bytes

ßŒḊ¡€Ṣ


Try it online!

## How it works

ßŒḊ¡€Ṣ - Main link f(M). Takes a multidimensional array M on the left
€  - Over each inner element E of M:
ŒḊ    -   Get its depth, D
ß  ¡   -   Call f(E) D times
Ṣ - Sort the result


Essentially, as sorting is idempotent, f is also idempotent, and so we can apply it as many times as we want with no extra side effects. Therefore, we iterate over each element of M, depth-wise, apply f to it, then sort the result.

# Wolfram Language (Mathematica), 18 bytes

Sort//@#/.Sort->D&


Try it online!

Essentially copied from this earlier answer. Relies on the array being rectangular; otherwise, LexicographicSort (introduced 12.3) is required instead

Sort//@#            sort all levels
/.Sort->D   un-Sort atoms

• Could you add an explanation? Normally I've seen // used like a pipe, and /@ as map, but I can't make sense of //@ here. Also, how does D (derivative) come into play? Is it something else here? Jan 24, 2022 at 1:00
• @Jonah //@ is MapAll, and D is identity when called on a single argument. That last part is necessary since e.g. Sort[1] does not become 1.
– att
Jan 24, 2022 at 1:22
• Thanks! Followup q: Why is the identity version of D not documented here? Or does it somehow fall out of the 1st or 3rd case? Jan 24, 2022 at 2:02
• @Jonah To be honest, I first found out while doing a brute-force search for identities. It does make sense in context of the 3rd case, though the presentation does imply that there needs to be at least one variable; deriving w.r.t. no variables is the same as not performing a derivation.
– att
Jan 24, 2022 at 2:38
• It is curious thatD doesn't throw an error when not given a differentiation variable. For example, you could also say Integrate@f is like doing an integration wrt no variables; but that returns an error rather than f. Jan 25, 2022 at 2:53

# APL (Dyalog Extended), 18 12 bytes

Anonymous prefix lambda. Takes list of lists… as argument.

{×≡⍵:∧∇¨⍵⋄⍵}


Try it online!

{} "dfn"; argument is ⍵:

× [if] signum of
≡ depth of
⍵ argument
: (i.e. if the argument has depth) then:

∧ sort the
∇ recursion on
¨ each of
⍵  the argument

⋄ else:

⍵ return the argument

# SWI-Prolog, 7259 49 bytes

f([H|T],S):-f(H,Q),f(T,R),msort([Q|R],S).
f(E,E).


Try it online!

# Vyxal, 6 bytes

λ-[vxs


Try it Online!

-5 thanks to @emanresuA in vychat

## Explained

λ-[vxs
λ      # a lambda that takes a single argument n and:
-     #   subtracts n from itself (scalars return 0 which is falsey, lists return a list of 0s which is truthy) - borrowed from https://codegolf.stackexchange.com/a/241658/78850
[    #  and if that item is a list
vx  #    call this lambda on each item
s #    and sort the result


# Pari/GP, 34 bytes

f(a)=if(#a',vecsort(apply(f,a)),a)


Try it online!

# Ruby, 30 bytes

f=->b{b*0==0?b:b.map(&f).sort}


Try it online!

# JavaScript, 70 64 bytes

f=x=>x.sort(g=(a,b)=>1/a?a-b:f(a).some((c,i)=>a=g(c,f(b)[i]))*a)


Try it online!

Saved 6 bytes thanks to tsh.

• f=x=>x.sort(g=(a,b)=>1/a?a-b:f(a).some((c,i)=>a=g(c,f(b)[i]))*a)
– tsh
Jan 24, 2022 at 7:37
• @tsh Nice one. Thanks! Jan 24, 2022 at 15:28

# Python 3,  47  36 bytes

Saved 1 byte thanks to @Dialfrost, and 9 bytes thanks to @loopywalt

f=lambda l:l*0!=0==l.sort(key=f)or l

• 46 bytes Jan 24, 2022 at 13:27
• cheaper type check 40 bytes Jan 24, 2022 at 20:24
• @loopywalt Thank you so much, I'm also trying out l*0==[] atm, I think it achieves the same of reducing the list to an empty state, with one byte less. Jan 25, 2022 at 8:19
• Good point! And you can save another one going l*0!=0. Jan 25, 2022 at 8:39
• While you're at it: 36. Jan 25, 2022 at 8:47

# J, 30 bytes

[:><@#\.@$(4 :'/:"x~y')&.>/@,<  Try it online! Uses a single fold to explicitly sort each rank, in order. Requires an explicit verb since rank " is a conjunction. Note: Could save 1 byte with {{ }} but it fails on TIO's J version. # J, 23 17 bytes, port of Adam's recursive APL solution [:/:~$:^:(#@$)"_1  Try it online! -6 thanks to ovs! • 17 bytes on the second one by using ^: instead of @.. – ovs Jan 23, 2022 at 23:21 • Nice one. Now, if you wish to play hard mode, please have a shot at this monstrosity. Jan 23, 2022 at 23:28 # Haskell + hgl, 15 bytes x=Fe<sr<m x*~|p  Takes input as a free monad of lists. ## Explanation In Haskell we use a free monad of lists. A very simplified definition would look like: data Ragged a = Pur a | Fe [Ragged a]  It's either a terminal element (wrapped in Pur) or a list of more ragged lists (wrapped in Fe). We could write the code then like: x (Fe y)= Fe < sr < m x$ y
x (Pur y)=
p y


In the Fe case we map x across the input to sort all lower levels, sort the result and wrap it back in a free.

In the pure case we just wrap it back in a pure using p.

Now hgl has a special operator to do this sort of case for us. We use the *~| operator which is the equivalent to a pattern match on the cases of a Free.

So now we rewrite both options as a function Fe<sr<m x and p and supply them as args to *~|.

We can't get rid of the x= this time because the definition is recursive.

## Reflections

Wow, I couldn't get this one in point free. That's probably an issue.

hoF for hoistFree nearly is useful here. If we just wanted to for example reverse every level hoF rv would work fine. But we can't just place sr in there instead of rv. sr needs the elements to be Ord. Instead we have to do this.

There should probably be a version of hoist which allows this sort of thing. Would save 9 bytes here.

maF ::
( Functor f
, Functor g
)
=> (f (Free g a) -> g (Free g a)) -> Free f a -> Free g a


# BQN, 13 bytesSBCS

⊢{∧⚇𝕨𝕩}´≡-↕∘≡


Run online!

{∧𝕊⍟≡¨𝕩} is a translation of J, {×≡𝕩?∧𝕊¨𝕩;𝕩} is a shorter direct translation of dyalog extended, but using the depth modifier is cooler.

• ⊢{∧⚇𝕨𝕩}´≡-↕∘≡
Jan 24, 2022 at 8:11
• The recursive version could be {∧𝕊⍟=˘𝕩} if you take an actual array
– ovs
Jan 24, 2022 at 9:23
• question says depth, so dunno if that will be right Jan 24, 2022 at 10:37
• The input is a rectangular array, so it can be represented by an array. And = and ˘ for an array are the same as ≡ and ¨ for an equivalent nested list. This is the same as the 17 byter on the J answer. (That means {∧𝕊⍟≡¨𝕩} works for your current input format)
– ovs
Jan 24, 2022 at 10:55
• ah i see, i'll put it in Jan 24, 2022 at 11:38

# 05AB1E, 15 bytes

"Ð˜Êi®δ.V}{"©.V


Explanation:

As mentioned in similar challenges, 05AB1E lacks recursive functions unfortunately, making it pretty long by mimicking the behavior with a string and 05AB1E-eval.

"..."       # Push the recursive string mentioned below
©      # Store it in variable ® (without popping)
.V    # Evaluate and execute it as 05AB1E code
# (after which the result is output implicitly)

Ð˜Ê         # Check that this is the maximum depth of this (inner) list:
Ð           #  Triplicate the current list
˜          #  Flatten the top copy
Ê         #  Check that the top two copies are NOT equal
i    }   # If this is truthy, so we've reached the maximum depth:
δ      #  Map over each inner item:
® .V    #   Do a recursive call (by 05AB1E-evaluating string ®)
{  # Sort the list


# Julia 1.0, 22 bytes

!x::Int=x
!x=sort(.!x)


Try it online!

# Charcoal, 49 bytes

⊞υθＦυＦιＦ⁼κ⁺⟦⟧κ⊞υκＷ∧υ⊟υ«≔⟦⟧ηＷι⊞η⊟ιＷ⁻ηιＦ№η⌊κ⊞ι⌊κ»Ｉθ


Try it online! Link is to verbose version of code. Outputs using Charcoal's default output format, where depth 1 arrays print their elements on their own line but the arrays themselves are double-spaced from each other, then depth 2 arrays are triple-spaced from each other etc. Explanation:

⊞υθ


Start enumerating all of the arrays at each depth.

ＦυＦι


Process all elements of each array.

Ｆ⁼κ⁺⟦⟧κ⊞υκ


If this element is itself an array then push it to the list of all arrays.

Ｗ∧υ⊟υ«


Process the list in reverse order.

≔⟦⟧ηＷι⊞η⊟ι


Move the elements from this array into a temporary array.

Ｗ⁻ηιＦ№η⌊κ⊞ι⌊κ


Move them back in ascending order.

»Ｉθ


Output the final array.

• neil how ru so good at this language and quick qns, how do you understand it? its not in english? Jan 24, 2022 at 13:27
• @DialFrost Verbose mode is almost readable. -v tells Charcoal to convert from Verbose mode to proper Charcoal, and -l tells it to print that before executing it.
– Neil
Jan 24, 2022 at 13:34
• oh ic thats why although i still dont understand this language haha Jan 24, 2022 at 14:06

# Fig, $$\7\log_{256}(96)\approx\$$ 5.762 bytes

!#lxKMX


See the README to see how to run this

This answer uses that fact that programs = functions in Fig, so I can invoke the program from within the program.

!#lxKMX # Takes the list as input
!       # If
#lx    # The input is a list
M  # Map the list
X # By this function (i.e. the program itself)
K   # Then sort the resulting list
# If the input is not a list, simply return the input
`
• But Vyxal does beat this Jul 23, 2022 at 3:32
• @emanresuA but not posted :) Jul 24, 2022 at 0:34