# Minimally sort a list into a matrix

Given an unsorted list of unique strictly positive integers, minimally sort it into a 2D matrix. The input list is guaranteed to be of composite length, which means the output matrix is not necessarily square, but is of size n x m with n,m > 1.

"Minimally sort" here means the following:

• Sort the list in ascending order.
• Compact the output matrix as much as possible -- minimize the sum of the dimensions of the matrix (for example, for 20 input elements as input, a 5x4 or 4x5 output matrix is required, and not a 2x10).
• Compact the sorted numbers as far to the upper-left of the matrix as possible, starting with the first element in the sorted list.
• This can be thought of as sorting the list, then slicing it along the matrix's anti-diagonals, starting with the upper-left.

## Examples:

For input 1..20 output is either a 5x4 or a 4x5 matrix as follows:

 1  2  4  7 11
3  5  8 12 15
6  9 13 16 18
10 14 17 19 20

1  2  4  7
3  5  8 11
6  9 12 15
10 13 16 18
14 17 19 20


For input [3, 5, 12, 9, 6, 11] output is a 2x3 or 3x2 as follows

3  5  9
6 11 12

3  5
6  9
11 12


For input [14, 20, 200, 33, 12, 1, 7, 99, 58], output is a 3x3 as follows

 1   7  14
12  20  58
33  99 200


For input 1..10 the output should be a 2x5 or 5x2 as follows

1 2 4 6  8
3 5 7 9 10

1  2
3  4
5  6
7  8
9 10


For input [5, 9, 33, 65, 12, 7, 80, 42, 48, 30, 11, 57, 69, 92, 91] output is a 5x3 or 3x5 as follows

 5  7 11 33 57
9 12 42 65 80
30 48 69 91 92

5  7 11
9 12 33
30 42 57
48 65 80
69 91 92


### Rules

• The input can be assumed to fit in your language's native integer type.
• The input and output can be given by any convenient method.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
• Oh, wow, a word I haven't seen since Linear Algebra; easily overlooked. My apologies. Feb 16, 2018 at 17:37
• @LuisMendo Added a 15 element test case. Feb 16, 2018 at 19:04

# Jelly, 2422 20 bytes

pS€ỤỤs
LÆDżṚ$SÞḢç/ịṢ  Try it online! Saved 2 bytes thanks to @Jonathan Allan. ## Explanation pS€ỤỤs Helper link. Input: integer a (LHS), integer b (RHS) p Cartesian product between [1, 2, ..., a] and [1, 2, ..., b] S€ Sum each pair Ụ Grade up Ụ Grade up again (Obtains the rank) s Split into slices of length b LÆDżṚ$SÞḢç/ịṢ  Main link. Input: list A
L              Length
ÆD            Divisors
$Monadic pair Ṛ Reverse ż Interleave Now contains all pairs [a, b] where a*b = len(A) SÞ Sort by sum Ḣ Head (Select the pair with smallest sum) ç/ Call helper link Ṣ Sort A ị Index into sorted(A)  • L%J¬TżṚ$ -> LÆDżṚ$ should save two I think Feb 16, 2018 at 19:18 • The first link can become pSÞỤs. Apr 24, 2018 at 16:42 # Python 2, 160158153 151 bytes -2 bytes thanks to Erik the Outgolfer -2 bytes thanks to Mr. Xcoder s=sorted(input()) l=len(s) x=int(l**.5) while l%x:x+=1 n=1 o=eval(l/x*[[]]) while s: for i in range(l/x)[max(0,n-x):n]:o[i]+=s.pop(0), n+=1 print o  • I belive you can use max(0,n-x) for -2 bytes. Feb 16, 2018 at 17:32 # R 110 95 bytes function(x){n=sum(x|1) X=matrix(x,max(which(!n%%1:n^.5))) X[order(col(X)+row(X))]=sort(x) t(X)}  Try it online! ### How it works f <- function(x) { n <- sum(x|1) # length p <- max(which(!n%%1:n^.5)) # height of matrix X <- matrix(x, p) # initialize matrix X[order(col(X) + row(X))] <- sort(x) # filling the matrix using position distance to the top left corner t(X) # probably required by OP }  Giuseppe saved a whopping 15(!) bytes by the following tricks • replacing length(x) by sum(x|1) (-1 byte) • floor() is not required as : rounds down anyway (-7) • ^.5 is shorter than sqrt() (-3) • using col(X) + row(X) instead of outer (nice!) • could not get rid of the t(X) though - disappointing ;) ### Original solution function(x){ n=length(x) p=max(which(!n%%1:floor(sqrt(n)))) X=outer(1:p,1:(n/p),+) X[order(X)]=sort(x) t(X)}  It would look more fancy with outer being replaced by row(X)+col(X), but that would require to initialize the output matrix X first. Try it online! • Very nice! You can get down to 95 bytes Feb 17, 2018 at 2:10 • Might be able to use something from my solution to a related challenge to help here as well. Apr 25, 2018 at 11:29 • It is indeed closely related. Very nice approach! Apr 25, 2018 at 11:53 # JavaScript (ES6), 172 bytes l=>(n=l.sort((a,b)=>b-a).length,w=l.findIndex((_,i)=>!(i*i<n|n%i)),a=l=>[...Array(l)],r=a(n/w).map(_=>a(w)),a(w+n/w).map((_,x)=>r.map((s,y)=>x-y in s&&(s[x-y]=l.pop()))),r)  ## Explanation l=>( // Take a list l as input l.sort((a,b)=>b-a), // Sort it n=l.length, // Get the length n w=l.findIndex((_,i)=>!(i*i<n|n%i)),// Find the first integer w where w >= √n and n % w = 0 a=l=>[...Array(l)], // Helper function a r=a(n/w).map(_=>a(w)), // Create the grid r of size w, n/w a(w+n/w).map((_,x)=> // For every x from 0 to w + n/w: r.map((s,y)=> // For every row s in r: x-y in s&&( // If the index x-y is in s: s[x-y]=l.pop()))), // Set s[x-y] to the next element of l r) // Return r  ## Test Cases f=l=>(n=l.sort((a,b)=>b-a).length,w=l.findIndex((_,i)=>!(i*i<n|n%i)),a=l=>[...Array(l)],r=a(n/w).map(_=>a(w)),a(w+n/w).map((_,x)=>r.map((s,y)=>x-y in s&&(s[x-y]=l.pop()))),r) l=m=>console.log(JSON.stringify(m)) l(f([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])) l(f([3,5,12,9,6,11])) l(f([14,20,200,33,12,1,7,99,58])) l(f([1,2,3,4,5,6,7,8,9,10])) # Perl 5, 132 bytes sub d{$,=0|sqrt(@_=sort{$a-$b}@_);--$,while@_%$,;map{$r++,$c--for@_/$,..$c;$a[$r++][$c--]=$_;$c=++$i,$r=0if$r<0||$c<0||$r>=\$,}@_;@a}


Try it online!

Subroutine returns a 2-D array. TIO link includes footer code for displaying test result.

# Octave, 151 bytes

function f(v)n=floor(sqrt(l=nnz(v)));while i=mod(l,n);++n;end;A=nan(m=l/n,n);for k=[1:m 2*m:m:l];do A(k)=sort(v)(++i);until~mod(k+=m-1,m)|k>l;end;A'end


Using three different kinds of loop constructs.

Try it online!

Unrolled:

function f(v)
n = floor(sqrt(l=nnz(v)));

while i = mod(l,n);
++n;
end;

A = nan(m=l/n, n);

for k = [1:m 2*m:m:l];
do
A(k) = sort(v)(++i);
until ~mod(k+=m-1, m) | k>l;
end;

A'
end

• Nice answer! Why is the ' in nnz(v') required? Feb 18, 2018 at 4:34
• @LuisMendo Thanks! Turns out the ' is not required if I wrap the range expression, e.g. 1:20, around brackets ([1:20]) at the call site (to make it an actual vector). Apparently in Octave, the colon operator doesn't create a vector, but a range constant that takes much less space in memory. For some reason, nnz() doesn't work with that type, but transposing the range constant yields a vector, so it works with the apostrophe. Calling the function with an actual vector removes the need for the '. Feb 18, 2018 at 13:06
• Thanks for the explanation. I didn't know that a range expression had that special treatment in Octave. Anyway, the fact that it doesn't create a vector for memory efficiency should be transparent to the programmer. That is, the fact that nnz(1:20) doesn't work is probably a bug (max(1:20), sum(1:20) etc are valid). Feb 18, 2018 at 16:38
• We should report it. It might affect other functions than nnz . Do you want to do it yourself, or shall I? Feb 18, 2018 at 18:06
• Reported. It also affected MATL; now solved. Thanks for noticing this! Feb 18, 2018 at 18:44

# Husk, 15 bytes

ḟȯΛ≤Σ∂MCP¹→←½ḊL


This works by brute force, so longer test cases may time out. Try it online!

## Explanation

ḟȯΛ≤Σ∂MCP¹→←½ḊL  Implicit input, a list of integers x.
L  Length of x (call it n).
Ḋ   List of divisors.
½    Split at the middle.
→←     Take last element of first part.
This is a divisor d that minimizes d + n/d.
P¹       List of permutations of x.
MC         Cut each into slices of length d.
ḟ                Find the first of these matrices that satisfies this:
∂            Take anti-diagonals,
Σ             flatten them,
ȯΛ≤              check that the result is sorted (each adjacent pair is non-decreasing).


# JavaScript (ES6), 233 bytes

f=s=>{l=s.length;i=Math.sqrt(l)|0;for(;l%++i;);p=(x)=>(x/i|0+x%i)*l+x%i;m=[...Array(l).keys()].sort((x,y)=>p(x)-p(y));return s.sort((a,b)=>a-b).map((x,i)=>m.indexOf(i)).reduce((a,b,d,g)=>!(d%i)?a.concat([g.slice(d,d+i)]):a,[])}


Explanation

f=s=>{                         // Take array s of numbers as input
l=s.length                   // short-hand for length
i=Math.sqrt(l)|0             // = Math.floor(Math.sqrt(l))
for(;l%++i;);                // i = width
j=l/i                        // j = height

p=(x)=>(x/i|0+x%i)*l+x%i     // helper to calculate (sort-of) ~manhattan
// distance (horizontal distance weighted
// slightly stronger), from top-left corner
// to the number x, if numbers 0,...,l are
// arranged left-to-right, top-to-bottom
// in an l=i*j grid

m=[...Array(l).keys()]         // range array
.sort((x,y)=>p(x)-p(y)),       // manhatten-sorted, sort-of...

return s.sort((a,b)=>a-b)      // sort input array by numbers,
.map((x,i,w)=>w[m.indexOf(i)])    // then apply inverse permutation of the
// range-grid manhatten-sort mapping.
.reduce(                     // slice result into rows
(a,b,d,g)=>!(d%i)?a.concat([g.slice(d,d+i)]):a
,[]
)
}


# Java 10, 199188 186 bytes

a->{int j=a.length,m=0,n,i=0,k=0;for(n=m+=Math.sqrt(j);m*n<j;n=j/++m);var R=new int[m][n];for(java.util.Arrays.sort(a);i<m+n;i++)for(j=0;j<=i;j++)if(i-j<n&j<m)R[j][i-j]=a[k++];return R;}


Try it online.

Explanation:

a->{                        // Method with int-array parameter and int-matrix return-type
int j=a.length,           //  Length of the input-array
m=0,n,                //  Amount of rows and columns
i=0,k=0;              //  Index integers
for(n=m+=Math.sqrt(j);   //  Set both m and n to floor(√ j)
m*n<j;               //  Loop as long as m multiplied by n is not j
n=j/++m);            //   Increase m by 1 first with ++m
//   and then set n to j integer-divided by this new m
var R=new int[m][n];     //  Result-matrix of size m by n
for(java.util.Arrays.sort(a);
//  Sort the input-array
i<m+n;)              //  Loop as long as i is smaller than m+n
for(j=0;j<=i;j++)      //   Inner loop j in range [0,i]
if(i-j<n&j<m)        //    If i-j is smaller than n, and j smaller than m
//    (So basically check if they are still within bounds)
R[j][i-j]=a[k++];  //     Add the number of the input array at index k,
//     to the matrix in the current cell at [j,i-j]
return R;}                //  Return the result-matrix


# C (gcc), 269253 226 bytes

j,w,h,x,y;c(int*a,int*b){a=*a-*b;}f(A,l)int*A;{int B[l];qsort(A,l,4,c);for(w=h=j=2;x=w*h-l;j++)l%j||(w=h,h=j),w=h*h-l?w:j;for(;j=x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h?B[x-y+y*w]=*A++:0;for(;j<l;printf("\n%d "+(j++%w>0),B[j]));}


Try it online!

# C (gcc), 214 bytes, using -zexecstack-lambdas

• Thanks to ceilingcat for this hackier, yet slimmer version.
j,w,h,x,y;f(A,l)int*A;{int B[l];qsort(A,l,4,L"\x62b078bǃ");for(w=h=j=2;x=w*h-l;j++)l%j||(w=h,h=j),w=h*h-l?w:j;for(;j=x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h?B[x-y+y*w]=*A++:0;for(;j<l;printf("\n%d "+(j++%w>0),B[j]));}


Try it online!

• @ceilingcat Thank you. May 24, 2020 at 22:47
• @ceilingcat Thank you. I assume you implemented a 'lambda' -- giving qsort a function pointer disguised as a wide-character string? Whilst I appreciate the solution, I added it as an addendum as I feel it is a tad too briddle to qualify as generic 'C'. May 26, 2020 at 0:41
• no "lambda" 225 bytes May 26, 2020 at 1:31
• @ceilingcat Thank you. May 26, 2020 at 1:34