7

Given the following 2d array:

6   8   11  17
9   11  14  20
18  20  23  29
24  26  29  35

Each row and column is sorted as well as the diagonals are sorted too (top left to bottom right). Assuming we have n² elements in the array (n = 4 in this case), it is trivial to use quicksort which takes O(n² log(n²)) = O(n² log(n)) to sort the 2d array. My question is can we sort this in O(n²)?

The goal is to use the given semi-sorted 2d array and come-up with a clever solution.

The target output is:

6   8   9   11
11  14  17  18
20  20  23  24
26  29  29  35
4
  • How O(n² log(n)) has been deducted? 2d array can be viewed as 1d array considering implementing an adequate technique of elements addressing. In this case, we should have O(n²) worst case despite the additional overhead on addressing.
    – cassandrad
    Commented May 28, 2020 at 11:57
  • 1
    We are assuming we have n² elements in the 2d array and it happen that n=4 in the example given. Commented May 28, 2020 at 12:10
  • What kind of complexity are you interested in? Average case or worst case? Commented Jun 3, 2020 at 18:03
  • @ReinhardMänner either is good enough :). Commented Jun 3, 2020 at 19:47

1 Answer 1

4
+50

Yes, we can sort this in O(n^2) time.

Reduction to sorting a 1D array

Let us first show that this new problem of sorting a 2D array (such that each row, column, and top-left-to-bottom-right diagonal is sorted) can be reduced to the problem of sorting a 1D array of n^2 elements.

Suppose we have a sorted 1D array of n^2 elements. We can trivially rearrange this in to a sorted n x n array by setting the first n numbers as the first row, followed by the next n numbers as the second row, and repeat until we exhaust the array.

Hence, given a 2D array of n^2 numbers, we can transform it into a 1D array in O(n^2) time, sort this array, then transform it back to the desired 2D array in O(n^2) time. Thus, if we can find a sorting algorithm for a 1D array in O(n^2), we can equivalently solve this new problem in O(n^2) time.

Sorting a 1D array in linear time

Given this, we simply need to provide a linear time sort. i.e. given n^2 elements, sort them in O(n^2) time. Conveniently, there are multiple algorithms you can use to accomplish this such as counting sort or radix sort, although they do come with various caveats. However, assuming a reasonable range of numerical values given the number of items to be sorted, these sorts will run in linear time.

Thus given n^2 elements in an n x n array, this 2D sorting problem can be reduced in O(n^2) time to a 1D sorting problem, which can then be solved with various linear time sorting algorithms in O(n^2) time. Hence, overall, this problem can be solved in O(n^2) time.

Sorting with a comparison sort

Following the discussion in the comments, the next step is to ask: what about comparison sorts. Comparison sorts are beneficial because it would allow us to avoid the previously mentioned caveats of counting and radix sorts.

However, even with this additional information, a linear time comparison sort is unlikely in practice, because this would require us to compute the final position of each number in O(1) time. We know this isn't possible using a comparison sort.

Let's consider a small example: what should be the final sorted position of the number originally in row 1, column 2? We know that it has to be the first of the numbers in columns 2...n. However, we don't know where it belongs relative to the numbers in column 1 (other than the number in row 1, column 1).

In general, for any number in the original square, we are uncertain of its final sorted position relative to all numbers to its lower left and the numbers to its upper right. It would take O(log_2(n)) comparisons to find the relative position of each number, and there are O(n^2) numbers to position. This uncertainty prevents us from achieving a linear time sort in practice.

But the additional information that we have should allow us to achieve some speedups. For example, we could adapt merge sort to this problem. In a standard merge sort we start by splitting our original array into half and repeat until we have arrays of size 1 that are guaranteed to be sorted, then we repeatedly merge these subarrays until we have one single array. For n^2 elements, we have to create a binary tree with log_2(n^2) layers, and each layer takes O(n^2) time to merge.

Using the additional information in your problem setup, we don't have to split the arrays until they are of size 1. Instead, we can start off with n sorted arrays of length n and start merging from there. This halves the number of layers we have to merge, and gives us a final runtime of O(n^2 log_2(n)).

Conclusion

In practice, this additional information allows some speedups for comparison sorts, allowing us to achieve O(n^2 log_2(n)) run times.

But in order to achieve a linear time sort that runs in O(n^2) time, we have to rely on algorithms such as counting or radix sort.

9
  • Thank you for the response (+1). I see that your solution boils down to using counting/radix sort. This is theortically correct but not practically. For example, if we had 10000 small integers (between 1 and 10) and only one of them was 2,147,000,000, then both sorting algorithms will be very inefficient and we are better off just using quicksort instead. The idea of the question is not to just use a linear algorithm. I am looking for a way based on how the array is semi-sorted. Commented May 29, 2020 at 14:24
  • I also added a sample output. Commented May 29, 2020 at 14:28
  • Ah, so if I'm understanding you correctly, you want to know if the semi-sorted arrays give us enough information to implement a faster comparison sort (that performs invariant of the range or type of numbers being sorted). Unfortunately, even in this case, we cannot outperform sorting algorithms such as quicksort. I'll add in an elaboration on why. Commented May 29, 2020 at 15:51
  • ^I retract this statement. A linear time comparison sort might be theoretically possible given this additional information. Quick sketch: each sorted row and column reduces the final number of permutations by a factor of n!, which means that the total number of possible permutations is now (n^2)!/(n!)^(2n). Assuming we use a binary decision tree where each node is a comparison that halves the search space, this takes log_2((n^2)!/(n!)^(2n)) <= (n^2)/log(2) comparisons Commented May 30, 2020 at 3:56
  • Please explain (n^2)!/(n!)^(2n), more precisely, the ^(2n) part. Commented May 30, 2020 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.