Given a matrix A, we can say that it is "sorted" if each row and column of A is sorted (ascending left-to-right for rows and top-to-bottom for columns). Thus, this matrix is sorted:
[ 1 2 3 4 5 ]
[ 2 2 3 4 5 ]
[ 3 3 3 4 5 ]
[ 4 4 4 4 5 ]
[ 5 5 5 5 5 ]
However, this matrix is not sorted:
[ 1 2 3 4 5 ]
[ 2 1 3 4 5 ]
[ 3 3 3 4 5 ]
[ 4 5 4 5 5 ]
[ 5 5 5 5 5 ]
The second column (transpose of [2, 1, 3, 5, 5]) and fourth row ([4, 5, 4, 5, 5]) are not sorted in ascending order.
Given a matrix (either as a 2D rectangular nested list or a string with consistent, distinct delimiters between rows and between values) and optionally the width and/or height of the matrix, output a sorted matrix (in the same format) with the same dimensions and containing the same values as the input matrix.
The values in the matrix will always be in the inclusive range [-128, 127] (8-bit signed two's complement integers). There is no limit on the dimensions of the input matrix.
##Examples
Because there are multiple valid outputs for each input, these are possible outputs. Any output that fulfills the conditions is valid. The examples are given with Python list notation.
[[-127, 14]] -> [[-127, 14]]
[[-122, -119, -105, -11], [-113, -63, -6, 39], [-34, 13, 47, 76], [37, 66, 93, 126]] -> [[-122, -119, -105, -11], [-113, -63, -6, 39], [-34, 13, 47, 76], [37, 66, 93, 126]]
[[-128, -128, -118, -108, -40, -13], [-119, -111, -108, -40, -12, 11], [-109, -61, -35, -12, 11, 52], [-48, -15, -8, 19, 74, 83], [-14, -1, 28, 74, 85, 112], [1, 32, 76, 88, 125, 127]] -> [[-128, -128, -118, -108, -40, -13], [-119, -111, -108, -40, -12, 11], [-109, -61, -35, -12, 11, 52], [-48, -15, -8, 19, 74, 83], [-14, -1, 28, 74, 85, 112], [1, 32, 76, 88, 125, 127]]
[[-113, -103, -97, -70, -57, -44, -28], [-99, -92, -67, -52, -40, -26, 40], [-87, -60, -52, -37, 7, 43, 61], [-58, -51, -37, 21, 53, 72, 87], [-45, -31, 25, 56, 76, 88, 99], [-29, 35, 57, 83, 89, 117, 120], [35, 60, 83, 97, 119, 124, 124]] -> [[-113, -103, -97, -70, -57, -44, -28], [-99, -92, -67, -52, -40, -26, 40], [-87, -60, -52, -37, 7, 43, 61], [-58, -51, -37, 21, 53, 72, 87], [-45, -31, 25, 56, 76, 88, 99], [-29, 35, 57, 83, 89, 117, 120], [35, 60, 83, 97, 119, 124, 124]]
[[-126, -125, -121, -101, -86, -66, -52, -40, -24, 3], [-122, -107, -98, -80, -65, -51, -40, -20, 5, 23], [-107, -93, -74, -65, -50, -38, -20, 7, 29, 43], [-91, -70, -58, -46, -37, -19, 8, 35, 49, 64], [-70, -56, -44, -33, -13, 8, 35, 50, 65, 78], [-52, -42, -27, -12, 10, 35, 50, 66, 80, 90], [-41, -24, 0, 11, 36, 61, 70, 81, 92, 106], [-24, 1, 16, 40, 61, 71, 84, 94, 107, 111], [2, 18, 42, 62, 72, 85, 98, 108, 114, 124], [19, 43, 63, 72, 89, 104, 109, 122, 125, 126]] -> [[-126, -125, -121, -101, -86, -66, -52, -40, -24, 3], [-122, -107, -98, -80, -65, -51, -40, -20, 5, 23], [-107, -93, -74, -65, -50, -38, -20, 7, 29, 43], [-91, -70, -58, -46, -37, -19, 8, 35, 49, 64], [-70, -56, -44, -33, -13, 8, 35, 50, 65, 78], [-52, -42, -27, -12, 10, 35, 50, 66, 80, 90], [-41, -24, 0, 11, 36, 61, 70, 81, 92, 106], [-24, 1, 16, 40, 61, 71, 84, 94, 107, 111], [2, 18, 42, 62, 72, 85, 98, 108, 114, 124], [19, 43, 63, 72, 89, 104, 109, 122, 125, 126]]
[[-128, -125, -123, -117, -105, -97, -82, -67, -40, -28, -5], [-123, -121, -109, -103, -94, -81, -58, -40, -25, -4, 16], [-119, -108, -102, -92, -81, -58, -39, -20, -4, 28, 45], [-107, -101, -90, -77, -57, -38, -20, -4, 29, 48, 60], [-101, -89, -69, -55, -37, -19, -1, 29, 51, 62, 81], [-83, -69, -48, -36, -16, 5, 30, 54, 70, 83, 92], [-68, -47, -32, -12, 6, 30, 57, 72, 84, 93, 98], [-40, -31, -10, 12, 31, 57, 74, 84, 93, 102, 108], [-29, -10, 12, 32, 58, 75, 85, 94, 104, 109, 115], [-9, 16, 33, 58, 79, 86, 97, 107, 113, 121, 123], [16, 38, 60, 80, 89, 97, 108, 114, 121, 124, 124]] -> [[-128, -125, -123, -117, -105, -97, -82, -67, -40, -28, -5], [-123, -121, -109, -103, -94, -81, -58, -40, -25, -4, 16], [-119, -108, -102, -92, -81, -58, -39, -20, -4, 28, 45], [-107, -101, -90, -77, -57, -38, -20, -4, 29, 48, 60], [-101, -89, -69, -55, -37, -19, -1, 29, 51, 62, 81], [-83, -69, -48, -36, -16, 5, 30, 54, 70, 83, 92], [-68, -47, -32, -12, 6, 30, 57, 72, 84, 93, 98], [-40, -31, -10, 12, 31, 57, 74, 84, 93, 102, 108], [-29, -10, 12, 32, 58, 75, 85, 94, 104, 109, 115], [-9, 16, 33, 58, 79, 86, 97, 107, 113, 121, 123], [16, 38, 60, 80, 89, 97, 108, 114, 121, 124, 124]]
[[-128, -128, -126, -118, -112, -106, -101, -93, -84, -69, -51, -38, -16, -4], [-126, -121, -117, -109, -106, -101, -91, -84, -67, -50, -36, -15, -4, 19], [-118, -114, -109, -105, -99, -89, -82, -65, -49, -33, -13, 0, 21, 35], [-112, -108, -105, -99, -87, -82, -64, -48, -33, -12, 1, 24, 35, 45], [-107, -104, -95, -87, -82, -64, -47, -32, -10, 4, 28, 38, 45, 60], [-103, -94, -85, -80, -60, -47, -32, -9, 7, 28, 38, 49, 63, 68], [-94, -85, -75, -59, -45, -32, -9, 8, 31, 39, 49, 63, 68, 80], [-85, -73, -57, -44, -26, -7, 10, 31, 40, 50, 64, 70, 81, 93], [-72, -52, -43, -21, -6, 11, 31, 41, 53, 64, 70, 83, 93, 108], [-52, -41, -20, -6, 12, 32, 42, 56, 65, 72, 87, 96, 109, 117], [-39, -19, -6, 13, 32, 43, 57, 66, 74, 87, 97, 110, 117, 120], [-17, -5, 18, 33, 44, 57, 67, 77, 88, 97, 112, 117, 121, 123], [-5, 19, 34, 44, 59, 68, 78, 91, 104, 113, 119, 122, 125, 126]] -> [[-128, -128, -126, -118, -112, -106, -101, -93, -84, -69, -51, -38, -16, -4], [-126, -121, -117, -109, -106, -101, -91, -84, -67, -50, -36, -15, -4, 19], [-118, -114, -109, -105, -99, -89, -82, -65, -49, -33, -13, 0, 21, 35], [-112, -108, -105, -99, -87, -82, -64, -48, -33, -12, 1, 24, 35, 45], [-107, -104, -95, -87, -82, -64, -47, -32, -10, 4, 28, 38, 45, 60], [-103, -94, -85, -80, -60, -47, -32, -9, 7, 28, 38, 49, 63, 68], [-94, -85, -75, -59, -45, -32, -9, 8, 31, 39, 49, 63, 68, 80], [-85, -73, -57, -44, -26, -7, 10, 31, 40, 50, 64, 70, 81, 93], [-72, -52, -43, -21, -6, 11, 31, 41, 53, 64, 70, 83, 93, 108], [-52, -41, -20, -6, 12, 32, 42, 56, 65, 72, 87, 96, 109, 117], [-39, -19, -6, 13, 32, 43, 57, 66, 74, 87, 97, 110, 117, 120], [-17, -5, 18, 33, 44, 57, 67, 77, 88, 97, 112, 117, 121, 123], [-5, 19, 34, 44, 59, 68, 78, 91, 104, 113, 119, 122, 125, 126]]
[[-125, -123, -123, -120, -117, -111, -105, -96, -88, -79, -67, -56, -44, -30, -21], [-123, -121, -118, -116, -110, -103, -95, -86, -76, -65, -55, -44, -30, -20, 0], [-121, -117, -114, -109, -102, -94, -85, -74, -64, -55, -43, -30, -19, 1, 17], [-117, -112, -108, -101, -93, -85, -74, -63, -54, -42, -29, -15, 3, 19, 34], [-112, -108, -100, -92, -83, -72, -61, -52, -41, -27, -14, 6, 21, 37, 54], [-107, -97, -91, -82, -72, -61, -52, -40, -27, -12, 7, 24, 37, 54, 67], [-96, -91, -81, -69, -60, -51, -39, -26, -11, 9, 24, 38, 55, 68, 78], [-91, -80, -69, -59, -49, -38, -26, -10, 11, 25, 38, 55, 68, 79, 85], [-79, -68, -59, -49, -37, -26, -9, 13, 27, 40, 56, 68, 80, 88, 96], [-67, -58, -47, -36, -25, -9, 13, 27, 40, 57, 68, 80, 90, 99, 106], [-57, -46, -32, -25, -7, 15, 29, 41, 57, 72, 80, 91, 100, 106, 110], [-45, -31, -24, -7, 15, 29, 41, 61, 72, 81, 93, 102, 107, 111, 116], [-31, -24, -6, 15, 32, 42, 62, 76, 82, 93, 102, 107, 111, 116, 118], [-23, -5, 16, 32, 44, 64, 76, 83, 94, 103, 110, 114, 116, 118, 119], [0, 16, 33, 48, 66, 77, 83, 94, 103, 110, 115, 117, 119, 119, 120], [17, 34, 53, 66, 78, 85, 96, 104, 110, 116, 118, 119, 120, 124, 126]] -> [[-125, -123, -123, -120, -117, -111, -105, -96, -88, -79, -67, -56, -44, -30, -21], [-123, -121, -118, -116, -110, -103, -95, -86, -76, -65, -55, -44, -30, -20, 0], [-121, -117, -114, -109, -102, -94, -85, -74, -64, -55, -43, -30, -19, 1, 17], [-117, -112, -108, -101, -93, -85, -74, -63, -54, -42, -29, -15, 3, 19, 34], [-112, -108, -100, -92, -83, -72, -61, -52, -41, -27, -14, 6, 21, 37, 54], [-107, -97, -91, -82, -72, -61, -52, -40, -27, -12, 7, 24, 37, 54, 67], [-96, -91, -81, -69, -60, -51, -39, -26, -11, 9, 24, 38, 55, 68, 78], [-91, -80, -69, -59, -49, -38, -26, -10, 11, 25, 38, 55, 68, 79, 85], [-79, -68, -59, -49, -37, -26, -9, 13, 27, 40, 56, 68, 80, 88, 96], [-67, -58, -47, -36, -25, -9, 13, 27, 40, 57, 68, 80, 90, 99, 106], [-57, -46, -32, -25, -7, 15, 29, 41, 57, 72, 80, 91, 100, 106, 110], [-45, -31, -24, -7, 15, 29, 41, 61, 72, 81, 93, 102, 107, 111, 116], [-31, -24, -6, 15, 32, 42, 62, 76, 82, 93, 102, 107, 111, 116, 118], [-23, -5, 16, 32, 44, 64, 76, 83, 94, 103, 110, 114, 116, 118, 119], [0, 16, 33, 48, 66, 77, 83, 94, 103, 110, 115, 117, 119, 119, 120], [17, 34, 53, 66, 78, 85, 96, 104, 110, 116, 118, 119, 120, 124, 126]]
[[-128, -128, -124, -123, -119, -115, -112, -103, -94, -84, -77, -68, -55, -49, -42, -34, -24], [-128, -124, -122, -119, -115, -109, -103, -93, -84, -77, -66, -55, -48, -42, -34, -23, -10], [-123, -122, -118, -113, -109, -103, -89, -84, -74, -65, -55, -48, -41, -33, -23, -9, 7], [-121, -117, -112, -106, -102, -88, -83, -74, -65, -54, -47, -40, -33, -22, -9, 8, 21], [-116, -112, -106, -102, -87, -82, -73, -65, -53, -47, -40, -32, -21, -6, 10, 21, 29], [-112, -105, -102, -86, -82, -73, -62, -53, -47, -40, -31, -21, -3, 10, 21, 32, 44], [-104, -101, -85, -79, -72, -62, -53, -46, -40, -31, -21, -2, 10, 24, 32, 44, 55], [-98, -85, -79, -71, -60, -52, -45, -39, -31, -19, -2, 12, 24, 33, 44, 55, 65], [-84, -78, -71, -60, -52, -45, -39, -31, -17, 1, 13, 25, 33, 45, 55, 66, 80], [-78, -70, -58, -51, -44, -39, -29, -16, 1, 13, 26, 35, 48, 55, 66, 81, 88], [-69, -58, -50, -44, -37, -29, -15, 1, 13, 26, 36, 49, 55, 67, 82, 88, 94], [-56, -50, -44, -36, -28, -13, 1, 14, 27, 36, 50, 58, 68, 82, 88, 94, 99], [-49, -43, -36, -27, -13, 2, 15, 27, 36, 50, 59, 68, 82, 91, 95, 100, 110], [-43, -35, -26, -13, 2, 16, 27, 37, 50, 60, 68, 82, 91, 95, 100, 110, 112], [-35, -26, -12, 3, 18, 27, 39, 51, 61, 70, 85, 91, 96, 103, 110, 113, 115], [-25, -12, 3, 18, 27, 39, 51, 63, 70, 87, 91, 97, 103, 111, 113, 116, 119], [-11, 6, 18, 28, 40, 52, 63, 73, 87, 92, 97, 104, 112, 113, 116, 119, 119], [7, 20, 29, 41, 54, 64, 74, 87, 93, 97, 107, 112, 114, 117, 119, 124, 127]] -> [[-128, -128, -124, -123, -119, -115, -112, -103, -94, -84, -77, -68, -55, -49, -42, -34, -24], [-128, -124, -122, -119, -115, -109, -103, -93, -84, -77, -66, -55, -48, -42, -34, -23, -10], [-123, -122, -118, -113, -109, -103, -89, -84, -74, -65, -55, -48, -41, -33, -23, -9, 7], [-121, -117, -112, -106, -102, -88, -83, -74, -65, -54, -47, -40, -33, -22, -9, 8, 21], [-116, -112, -106, -102, -87, -82, -73, -65, -53, -47, -40, -32, -21, -6, 10, 21, 29], [-112, -105, -102, -86, -82, -73, -62, -53, -47, -40, -31, -21, -3, 10, 21, 32, 44], [-104, -101, -85, -79, -72, -62, -53, -46, -40, -31, -21, -2, 10, 24, 32, 44, 55], [-98, -85, -79, -71, -60, -52, -45, -39, -31, -19, -2, 12, 24, 33, 44, 55, 65], [-84, -78, -71, -60, -52, -45, -39, -31, -17, 1, 13, 25, 33, 45, 55, 66, 80], [-78, -70, -58, -51, -44, -39, -29, -16, 1, 13, 26, 35, 48, 55, 66, 81, 88], [-69, -58, -50, -44, -37, -29, -15, 1, 13, 26, 36, 49, 55, 67, 82, 88, 94], [-56, -50, -44, -36, -28, -13, 1, 14, 27, 36, 50, 58, 68, 82, 88, 94, 99], [-49, -43, -36, -27, -13, 2, 15, 27, 36, 50, 59, 68, 82, 91, 95, 100, 110], [-43, -35, -26, -13, 2, 16, 27, 37, 50, 60, 68, 82, 91, 95, 100, 110, 112], [-35, -26, -12, 3, 18, 27, 39, 51, 61, 70, 85, 91, 96, 103, 110, 113, 115], [-25, -12, 3, 18, 27, 39, 51, 63, 70, 87, 91, 97, 103, 111, 113, 116, 119], [-11, 6, 18, 28, 40, 52, 63, 73, 87, 92, 97, 104, 112, 113, 116, 119, 119], [7, 20, 29, 41, 54, 64, 74, 87, 93, 97, 107, 112, 114, 117, 119, 124, 127]]
[[-128, -126, -125, -122, -119, -115, -111, -105, -97, -91, -79, -71, -63, -55, -46, -38, -25, -9, 2], [-125, -123, -120, -118, -114, -111, -104, -96, -91, -79, -71, -61, -55, -45, -38, -24, -9, 2, 13], [-122, -120, -117, -114, -111, -104, -96, -90, -79, -70, -61, -55, -45, -37, -24, -9, 2, 14, 23], [-119, -116, -112, -110, -103, -95, -90, -79, -70, -61, -54, -45, -35, -23, -7, 3, 15, 25, 35], [-116, -112, -110, -103, -94, -89, -78, -70, -61, -54, -44, -35, -21, -7, 4, 15, 27, 37, 43], [-112, -108, -102, -94, -88, -77, -69, -60, -52, -44, -35, -21, -7, 4, 16, 27, 38, 44, 64], [-107, -102, -94, -87, -77, -68, -59, -51, -43, -35, -20, -5, 5, 16, 27, 38, 46, 65, 74], [-99, -93, -86, -77, -65, -59, -51, -43, -33, -20, -5, 5, 16, 28, 38, 47, 66, 74, 79], [-93, -85, -74, -65, -59, -51, -43, -33, -18, -4, 5, 16, 29, 39, 48, 66, 74, 79, 89], [-81, -74, -64, -58, -49, -43, -31, -17, -3, 5, 17, 29, 39, 50, 67, 75, 80, 90, 95], [-72, -64, -56, -49, -41, -31, -16, -3, 7, 17, 31, 40, 51, 67, 75, 81, 90, 95, 99], [-63, -56, -47, -40, -29, -14, -3, 9, 17, 32, 41, 51, 67, 75, 81, 91, 95, 99, 103], [-55, -47, -40, -28, -13, -2, 9, 18, 32, 41, 52, 67, 76, 82, 91, 96, 100, 107, 111], [-46, -39, -28, -11, -2, 11, 19, 32, 41, 54, 68, 76, 82, 91, 96, 100, 108, 113, 117], [-38, -26, -10, -2, 11, 20, 33, 41, 57, 68, 77, 82, 92, 97, 100, 108, 113, 117, 120], [-25, -10, 1, 11, 21, 35, 42, 57, 72, 77, 83, 92, 98, 100, 109, 113, 117, 121, 123], [-10, 1, 12, 21, 35, 42, 59, 72, 77, 84, 94, 99, 101, 110, 114, 119, 122, 124, 125], [2, 12, 21, 35, 42, 61, 73, 78, 84, 94, 99, 101, 110, 115, 119, 122, 125, 126, 127], [13, 21, 35, 42, 63, 74, 78, 87, 95, 99, 103, 110, 116, 119, 123, 125, 126, 127, 127]] -> [[-128, -126, -125, -122, -119, -115, -111, -105, -97, -91, -79, -71, -63, -55, -46, -38, -25, -9, 2], [-125, -123, -120, -118, -114, -111, -104, -96, -91, -79, -71, -61, -55, -45, -38, -24, -9, 2, 13], [-122, -120, -117, -114, -111, -104, -96, -90, -79, -70, -61, -55, -45, -37, -24, -9, 2, 14, 23], [-119, -116, -112, -110, -103, -95, -90, -79, -70, -61, -54, -45, -35, -23, -7, 3, 15, 25, 35], [-116, -112, -110, -103, -94, -89, -78, -70, -61, -54, -44, -35, -21, -7, 4, 15, 27, 37, 43], [-112, -108, -102, -94, -88, -77, -69, -60, -52, -44, -35, -21, -7, 4, 16, 27, 38, 44, 64], [-107, -102, -94, -87, -77, -68, -59, -51, -43, -35, -20, -5, 5, 16, 27, 38, 46, 65, 74], [-99, -93, -86, -77, -65, -59, -51, -43, -33, -20, -5, 5, 16, 28, 38, 47, 66, 74, 79], [-93, -85, -74, -65, -59, -51, -43, -33, -18, -4, 5, 16, 29, 39, 48, 66, 74, 79, 89], [-81, -74, -64, -58, -49, -43, -31, -17, -3, 5, 17, 29, 39, 50, 67, 75, 80, 90, 95], [-72, -64, -56, -49, -41, -31, -16, -3, 7, 17, 31, 40, 51, 67, 75, 81, 90, 95, 99], [-63, -56, -47, -40, -29, -14, -3, 9, 17, 32, 41, 51, 67, 75, 81, 91, 95, 99, 103], [-55, -47, -40, -28, -13, -2, 9, 18, 32, 41, 52, 67, 76, 82, 91, 96, 100, 107, 111], [-46, -39, -28, -11, -2, 11, 19, 32, 41, 54, 68, 76, 82, 91, 96, 100, 108, 113, 117], [-38, -26, -10, -2, 11, 20, 33, 41, 57, 68, 77, 82, 92, 97, 100, 108, 113, 117, 120], [-25, -10, 1, 11, 21, 35, 42, 57, 72, 77, 83, 92, 98, 100, 109, 113, 117, 121, 123], [-10, 1, 12, 21, 35, 42, 59, 72, 77, 84, 94, 99, 101, 110, 114, 119, 122, 124, 125], [2, 12, 21, 35, 42, 61, 73, 78, 84, 94, 99, 101, 110, 115, 119, 122, 125, 126, 127], [13, 21, 35, 42, 63, 74, 78, 87, 95, 99, 103, 110, 116, 119, 123, 125, 126, 127, 127]]
Huge thanks to Sp3000 for helping me out with this challenge in chat