Sorting A 2-D Array Of Integer Whose Rows & Column Elements Are Sorted

Merge the columns(or rows) using a merge method similar to one used in merge sort.

That would take advantage of the fact that each column is sorted by itself.

This should be fast enough.

EDIT

And it seems that there is a merge function already in the standard library. http://en.cppreference.com/w/cpp/algorithm/merge

I'd use some kind of algorithm similar to "flood fill" or path-finding algorithms like A*. Start in the upper left corner (value 1), output it and "expand" to the right and to the bottom - so add their values (2 and 5) to a list. Both of those will be greater than 1. Now output the smallest value from your list (value 2) and "expand" it, too. You'll get 4 and 7 added to your list, output 4 and "expand" it, and so on.

Note that by keeping the list sorted, you can output the smallest element instantly and might even be able to output multiple "runs" of consecutive values at once (f.e. 10,11,12). So pseudocode would be:

// array a[y][x]
// list L - ordered insertion, additionally stores matrix indices of values
add a[0][0] to L
loop until L is empty
  output first element of L
  remove first element of L and add its right and bottom neighbors (if any) to L
loop end

EDIT: Here's a working C implementation.

#include <stdio.h>
#include <stdlib.h>

#define COLS 5
#define ROWS 4

int matrix[ROWS][COLS] = {
   1,  5,   10,   15,  20,
   2,  7,   12,   17,  22,
   4,  9,   18,   25,  28,
   11, 14,  21,   26,  31
};

struct entry {
  int value;
  int x, y;
};

entry list[ROWS+COLS]; // Not sure how big the list can get, but this should be enough
int list_len = 0;

void set_list_entry(int index, int value, int x, int y) {
  list[index].value = value;
  list[index].x = x;
  list[index].y = y;
}

void add_to_list(int x, int y) {
  int val = matrix[y][x];
  int i, pos = list_len;

  for (i = 0; i < list_len; i++) {
    if (list[i].value == val) return; // Don't add value that is on the list already
    if (list[i].value > val) {
      pos = i;
      break;
    }
  }
  // Shift the elements after pos
  for (i = list_len + 1; i > pos; i--) {
    set_list_entry(i, list[i - 1].value, list[i - 1].x, list[i - 1].y);
  }
  // Insert new entry
  set_list_entry(pos, val, x, y);

  list_len++;
}

int main() {
  int iteration = 0;

  add_to_list(0,0);

  do {
    // output first element of list
    printf("%i ", list[0].value);
    iteration++;
    if ((iteration % COLS) == 0) printf("\n");
    // add neighbors of first element of list to the list
    if (list[0].x < (COLS - 1)) add_to_list(list[0].x + 1, list[0].y);
    if (list[0].y < (ROWS - 1)) add_to_list(list[0].x, list[0].y + 1);
    // remove first element of list
    for (int i = 0; i < list_len; i++) {
      set_list_entry(i, list[i + 1].value, list[i + 1].x, list[i + 1].y);
    }
    list_len--;
  } while (list_len > 0);

  return 0;
}

Note the comment about the list length. I'm not sure how big the list can get, but I think COLS+ROWS should be enough looking at this worst case:

1 3 5 7 9 ..
2 y y y y
4 y x x x
6 y x x x
8 y x x x
.
.

If all "border" elements are less than the smallest y value, you'll get a list full of the y values in the process, which is (ROWS - 1) + (COLS - 1) elements long.

Looking at such worst cases, I guess this is not the most efficient solution, but I think it's an elegant and concise one nevertheless.

why don't we consider this question as "merging N sorted list each has k elements".

creating a min-heap of k element. putting each smallest element of sorted list in that min-heap. popping root of the heap. now insert the next element of list whose element was the root. In this way we get complexity of N*k log(k).

in above case it will be N^2log(N), where N is number of element in one row.

Here's a hint - assuming that's a normal 2D C array, using a little bit of of typecasting, you should be able to interpret it as a 1D array.