Sort every dimension

Question

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]]]

Answer 1

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)

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

SWI-Prolog, 72 59 49 bytes

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

Try it online!

Answer 6

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

Answer 7

Pari/GP, 34 bytes

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

Try it online!

Answer 8

Ruby, 30 bytes

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

Try it online!

Answer 9

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.

Answer 10

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

Answer 11

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, ²³ 17 bytes, port of Adam's recursive APL solution

[:/:~$:^:(#@$)"_1

Try it online!

-6 thanks to ovs!

Answer 12

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

Answer 13

BQN, 13 bytes^SBCS

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

Run online!

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

-2 from Adam.

Answer 14

05AB1E, 15 bytes

"ИÊi®δ.V}{"©.V

Try it online or verify all test cases.

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

Answer 15

Julia 1.0, 22 bytes

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

Try it online!

Answer 16

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.

Answer 17

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