Double dimension array sorting in O(n) time

Question

I was asked a question in interview for sorting a double dimension array in O(n) time.How is it possible to do it in O(n).Can someone shed some light on it.. Thank you.

Input:

3 5 7 1
4 9 2 0
9 3 6 2   

Output

0 1 2 2 
3 3 4 5  
6 7 9 9

Answer 1

You can sort as a plain array.
E.g.

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


int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

#define ROW_SIZE 3
#define COL_SIZE 4

int main(void){
    int M[ROW_SIZE][COL_SIZE]={{3,5,7,1},{4,9,2,0},{9,3,6,2}};
    int c,r,*p;

    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
        for(c=0;c<COL_SIZE;++c){
            printf("%d ",*p++);
        }
        printf("\n");
    }
    printf("\n");
    qsort(&M[0][0], ROW_SIZE*COL_SIZE, sizeof(int), cmp);
    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
        for(c=0;c<COL_SIZE;++c){
            printf("%d ",*p++);
        }
        printf("\n");
    }

    return 0;
}

Answer 2

Don't know what did you actually mean by double dimension array, but there are sorting algorithms specific for some situations that can achieve O(n). An example of that is Counting sort, if you want to sort an array with 1000 integers in the range 1 to 1000, it can sort in O(n).

EDIT: The fact that it's a multidimensional array does not change logic of the sorting. You can convert the index (using by the sorting) to the bidimensional index like this:

array[i / N][i % N];

Where N is the size of the first dimension.