What algorithm suit me, with issue?

Question

I have a Matrix [M x N], in each cell of matrix, there is an array [N](sorted from max to min).

I have to write a function that reconstruct this Matrix to one data-structure, ordered from min to max?

With optimal memory and time.

My solution is not optimal and extremely highly costs (memory&time).
Solution: Iterate over the matrix and pull each array to one Array: O(N^2 - memory&time) after that sort this array O(N - memory&time).

What algorithm suits me best?

Something like [Tournament sort](https://en.wikipedia.org/wiki/Tournament_sort) can help when you are merging already sorted lists. — SWeko, Oct 02 '13 at 06:33
I don't understand. Since you have `N^3` elements and need to sort all of them, you cannot do better than `N^3` in both memory and time. And you say you have `N^2` "nonoptimal" solution. — Mikhail, Oct 02 '13 at 06:34
Have you tried some of merging technique? Maybe merge each cell one by one, when all rows are done you can merge the result from row with each other. — Tomas Jansson, Oct 02 '13 at 06:34
@Mikhail, the N^2 arrays are already sorted, so it might be possible to do better than the average complexity. — SWeko, Oct 02 '13 at 06:40
If the values are integers and if you know or can easily get the highest value and if that highest value isn't too high (a lot of *if*s), then maybe you could use [counting sort](http://en.wikipedia.org/wiki/Counting_sort). — Corak, Oct 02 '13 at 06:56
@SWeko: Still, there are `N^3` elements (or `M*N^2`, if you go by the edit). Is it possible to sort without looking at each of the elements at least once? — AbdullahC, Oct 02 '13 at 07:17

Tomas Jansson · Answer 1 · 2013-10-02T13:08:40.890

This answer might be a little bit off topic since it is using f# and not c#, however the algorithm could be reused but I thought it was faster to write it in f#. This is a sample solution where I merge all the results as described in my comment to the question:

let rec orderedMerge xs ys =
    match xs,ys with
    | [],l | l,[] -> l
    | x::xs', y::ys' ->
        if x < y then x :: (orderedMerge xs' ys)
        else y :: (orderedMerge xs ys')

let rec orderNestedMerge xxs =
    match xxs with
    | x::[] -> x
    | x::y::[] -> orderedMerge x y
    | x::y::xxs' -> orderedMerge (orderedMerge x y) (orderNestedMerge xxs')

let rec orderNested2Merge xxxs = 
    match xxxs with
    | x::[] -> orderNestedMerge x
    | x::y::[] -> orderedMerge (orderNestedMerge x) (orderNestedMerge y)
    | x::y::xxxs' -> orderedMerge (orderedMerge (orderNestedMerge x) (orderNestedMerge y)) (orderNested2Merge xxxs')

let l1 = [1;5;6;10]
let l2 = [2;3;9;11]
let l3 = [3;4;5;8]
let l4 = [2;8;9;12]
let m1 = [l1;l2]
let m2 = [[l1;l2];[l3;l4]]
let r1 = orderedMerge l1 l2
let r2 = orderNestedMerge m1
let r3 = orderNested2Merge m2

Results:

val m1 : int list list = [[1; 5; 6; 10]; [2; 3; 9; 11]]
val m2 : int list list list = [[[1; 5; 6; 10]; [2; 3; 9; 11]]; [[3; 4; 5; 8]; [2; 8; 9; 12]]]
val r1 : int list = [1; 2; 3; 5; 6; 9; 10; 11]
val r2 : int list = [1; 2; 3; 5; 6; 9; 10; 11]
val r3 : int list = [1; 2; 2; 3; 3; 4; 5; 5; 6; 8; 8; 9; 9; 10; 11; 12]

I haven't calculated how it perform but I think it is quire well. On a side note, I don't think you can implement a solution that has both optimal memory and time utilization, you have to focus one of them first and then make the other one as good as possible.

UPDATE: One improvement you could do to this solution is to use tail recursion, it shouldn't be that hard to rewrite it to use tail recursion.

@IamStalker Maybe later, don't have time now. Doing it in c# is much more verbose than in f#. If you provide your starting data structures it would be much less to write to get it going, so please provide those in your question. — Tomas Jansson, Oct 03 '13 at 09:28

score 0 · Answer 2 · answered Oct 02 '13 at 12:59

You are basically trying to implement merge sort, but with part of the sub cases already sorted. If you just recursively merge pairs of lists the way merge sort does, and assuming you actually meant that the length of the lists is approximately the same length as the length of a matrix side, then your run time is O(n^3 log(n^2)) rather than your original suggestion which is O(n^3 log(n^3)), or it's about 33% faster (I'm grossly misusing bigO notation here).

And that is what my provided solution does :). – Tomas Jansson Oct 02 '13 at 13:22 — Tomas Jansson, Oct 02 '13 at 13:22

score 0 · Answer 3 · edited May 23 '17 at 12:13

The algorithm you talk about cannot possibly have a time and space complexity of O(N^2). I've specified my analysis below:

Algorithm 1 - Complexity: O(MN^2 log (MN^2))

This is the algorithm you've described.

1) Iterate over the matrix and pull each array to one Array: It will take O(M*N^2) time to copy all the elements

2) After that sort this array. The fastest you could possibly sort is O(M*N^2 log (M*N^2)).

Thus, the overall time complexity will be O(M*N^2 log (M*N^2)).

Algorithm 2 - Complexity: O(MN^2 × log MN)

Adapted from Algorithm for n-way merge

Create a priority queue
Iterate through each array among the MxN arrays
1. enqueue the pair (nextNumberIn({i,j}th array), {i,j}) using the first value as priority key
While queue not empty
1. dequeue head (number, {i,j}) of queue
2. output number
3. if {i,j}th array not depleted
  1. enqueue (nextNumberIn({i,j}th array), {i,j})

Since adding elements to a priority queue can be done in logarithmic time, item 2 is O(M*N × log M*N). Since (almost all) iterations of the while loop adds an element, the whole while-loop will be O(M*N^2 × log M*N), where M*N^2 is the total number of elements to sort.

Since the complexity for step 3 dominates, the overall time complexity will be O(M*N^2 × log M*N).

Space Complexity

For both the algorithms above, the space complexity will be minimum of O(M*N^2) to store the new array. In addition to that, algorithm #1 will require about O(log (M*N^2)) additional space for the sorting step, while algorithm #2 will require an additional space of O(M*N) for the priority queue.

What algorithm suit me, with issue?

3 Answers3