Sorting numbers in an array are one of the most basic problems that we learn to solve and have always proved useful. Though there are many algorithms for sorting in 1 dimensional array of numbers, there are not many algorithms which can be applied to 2 dimension or higher dimension arrays. In this paper, we will discuss a new algorithm for sorting 2-dimensional array and will see how it can be modified to sort n-dimensional array.
Sorting is one of the very first problem that we learn. There are many sorting algorithms proposed
and some of the widely accepted ones include bubble sort, selection sort, insertion sort, quick sort [1],
merge sort [2] to name a few. These algorithms are fit for linear collection of data but mostly not for
complex data structures like tensors or multidimensional arrays. Among this, bubble sort, insertion sort
and selection sort have the overall time complexity of O(n2). Quick sort has an average case time
complexity as Ɵ(nlogn) but have a worst time complexity of O(n2). On the other hand, merge sort has
both average and worst time complexity of O(nlogn) but it uses extra space with worst case space
complexity as O(n). Many authors like Oyelami et. al. [
But very few works have been done in the field of multidimensional arrays. One of the interesting
works have been presented by Sandeep Sen et. al. [
We take a window of 2x2 for a 2-dimensional matrix of size m x n. So, the window will have the
elements (i,j), (i,j+1), (i+1,j) and (i+1,j+1) for all 0<=i<m and 0<=j<n. We start from the top left corner.
In doing so, we have four numbers under the window. We sort the four numbers and then rearrange the
four numbers within the window such that the smallest number is on the top left of the window, next
smallest number on the top right, next on the bottom left and the largest number on the bottom right of
the window. Now we slide the window one place to the right along the row and will repeat the process
until the we reach the end of the row, i.e., top right cell of the window is the last cell along the row. We
repeat this for all the rows. This total process forms one pass. We again start form the top left corner of
the new matrix until we have done max(m,n) passes. There will be some corner cases like when the
window moves to the end of a row or column, i+1 (or j+1) will be out of index range. For simplification,
we use mod number_of_rows and mod number_of_columns to locate the elements under the window.
A depiction of the process is shown in Fig. 2 and Fig. 3.
4. Pseudo Code
function window_sort(array[][], r, c):
//array[][] is the given array
// r is the number of rows
// c is the number of columns
flag := 0
for x := 0 to max(r,c) do:
for i := 0 to r-1 do:
for j := 0 to c-1 do:
k := (i+1) % r
l := (j+1) % c
a := min(i,k)
b := max(i,k)
c := min(j,l)
d := max(j,l)
array[a][c] := window[0]
array[a][d] := window[1]
array[b][c] := window[2]
array[b][d] := window[
break loop else do:
flag = 0
end if
end for
end function
window := [array[i][j], array[i][l], array[k][j], array[k][l]]
window := sort(window)
if array[a][c] ≠ window[0] or array[a][d] ≠ window[1] or array[b][c] ≠ window[2] or
array[b][d] ≠ window[
flag := 1 end if
When sorting the numbers in the window, we are every time sorting four number and place them at their respective positions in the window. It will take O(1) time. At every pass, we are sliding the window m*n times and this takes O(m*n). We are repeating the above steps for getting the array sorted and it will take a maximum of max(m,n) passes since a misplaced element needs to be moved a maximum of this distance to be placed in its right place. We may even stop the execution if there is no rearrangement during a pass by using a flag variable. Thus, the total time complexity in the worst case is O(m*n*max(m,n)). This can also be written as O((max(m,n))3) in the worst case. Since, we did not use any additional space, space complexity is O(1).
Let us extend this to 3-D array first with dimensions d1, d2 and d3. We take the window size as 2 x 2 x 2. The window will be in a shape of smaller cube where the 3-D array will be a bigger cube. The total number of elements under the window to be sorted first is 8. For now we can take the sorting time of the elements under the window be constant, i.e., O(1) as the number of elements under the window to be sorted is constant every time. Now, we move the smaller window cube over the whole array cube such that the (0,0,0) element of the smaller window cube coincides will all (i,j,k) of the bigger array for all 0<=i<d1, 0<=j<d2, 0<=k<d3. Thus, the time complexity of each pass will be O(d1 x d2 x d3). We have to do max(d1, d2, d3) passes as this will be the longest distance that a misplaced element have to be moved to its correct place. So, the total time complexity will be O(d1 x d2 x d3 x max(d1, d2, d3)). But as the dimension increases, the size of the window increases and hence the number of elements to be sorted each time. If we have n dimensions, the window size will be 2n and hence, we need to sort 2n elements each time.
Let us generalize for n-D array, we can choose the window size as 2 x 2 x 2 x… upto n times. Here, the total number of elements in the window will be 2n. Now, we can use the best existing algorithm for sorting the elements in the window and getting it to their proper positions within the window which will take O(n x logn) for n elements. In this case, this will take in the worst case, we have 2n elements, hence O(2n x log2n) or, O(2n x n x log2) or, O(2n x n)
Then we can follow the above explained procedure to first sort within the window and then slide the window. If di, for i from 1 to n, are dimension sizes of the n dimensions, then the total worse case time complexity of the given algorithm is
O(2n x n) x O(max(d1,d2,…,dn)^(n+1))
When this array is implemented for 1-D array, it will be similar to Bubble sort. But as it will go in higher dimension, its complexity will be better compared to other general sorting algorithm.
We know that most of the 1D sorting algorithms including quick sort [1] has worst time complexity O(n2). If we sort the 2-D array of size m x n by transforming it into a linear array, the number of elements become m*n and thus the time complexity becomes O(m2 x n2). On the other hand, the above proposed algorithm can do it more efficiently. Only merge sort [2] can do it differently with worst time complexity O(m x n x log(m x n)) but it will use extra space with space complexity O(m x n).
I would also like to thank Department of Computer Science & Engineering, Jadavpur University, Kolkata for giving me the platform to learn, grow, explore and research. Last but not the least, I would like to thank my parents and family for being the pillars of my life, without whom, nothing would have been possible.