/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int merge_sort(int sort[], int low, int high);
int merge(int sort[], int low, int mid, int high);

int** diagonalSort(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes){


int m=matSize, n=matColSize, i, j, k, diff, count;
    int sort[100];
               
    diff=n-2;
    while(1)
    {
        count = 0;
        for (i=0; i<m; i++)
        {
            if ( (i+diff)==n) break;
            sort[i] = mat[i][i+diff];
            count++;
        }
        merge_sort(sort, 0, count-1);
        for (i=0; i<count; i++)
            mat[i][i+diff] = sort[i];
        diff--;
        if (diff<0) break;
    }    
    
    diff=1; 
    while(1)
    {
        count = 0;
        for (i=diff, k=0; i<m; i++)
        {
            if ( (i-diff)==n) break;
            sort[k] = mat[i][i-diff];
            count++; k++;
        }
        
        merge_sort(sort, 0, count-1);
        
       for (i=diff, k=0; i<m; i++)
        {
            if ( (i-diff)==n) break;
            mat[i][i-diff] = sort[k]; 
            k++;
        }
               
        diff++;
        if(diff==m-1) break;
    }
    
   return mat;
}
          
int merge_sort(int sort[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        merge_sort(sort, low, mid);
        merge_sort(sort, mid + 1, high);
        merge(sort, low, mid, high);
    }
    return 0;
}

int merge(int sort[], int low, int mid, int high)
{
    int left[251], right[251];
    int n1, n2, i, j, k;
    
    n1 = mid - low + 1;
    n2 = high - mid;
    
    for (i = 0; i < n1; i++)
        left[i] = sort[low + i];
    for (j = 0; j < n2; j++)
        right[j] = sort[mid + j + 1];

    left[i] = right[j] = 9999;
    i = j = 0;
    
    for (k = low; k <= high; k++)
    {
        if (left[i] <= right[j])
            sort[k] = left[i++];
        else
            sort[k] = right[j++];
    }
    return 0;
}