Create sorted 1D array from sorted 2D array

Problem:

Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?

Solution:
A possible solution utilizes a propagating front separating the elements that have already been sorted into the 1D array from those that are still pending. The solution is \(\mathcal{O}(N)\) in space because of the storage required for the front and \(\mathcal{O}(N^3)\) in time as the insertion of each of the \(N^2\) numbers requires a comparison of the N front values (at most).

The algorithm generalizes to sorting \(D\)-dimensional arrays, in which case the front has dimension \(D-1\).

Compile with -std=c++11 and please leave comments if you find a mistake or an improvement.

#include <iostream>
#include <limits>

using namespace std;
// typedef double arraytype;
typedef int arraytype;

#define N 4                                                                     // example with a 4x4 matrix

const arraytype mat[N][N] = {{1,2,4,5},{2,3,5,7},{4,6,12,13},{5,20,21,22}};     // sorted 2D array

int main () {

    arraytype arr[N*N] = {0};                                                   // initialize the array to zero
    unsigned int front[N] = {0};                                                // use a front that contains the first number to consider for each column, i.e., 
                                                                                // the first number in each column that has not be sorted in the 1D array yet

    for ( unsigned int n = 0; n != N*N; ++n ) {                                 // loop the 1D array
        arraytype m = numeric_limits<arraytype>::max();                         // init smallest element found to max
        unsigned int f = 0;                                                     // variable for updating the front in one column
        for ( unsigned int col = 0; col != N; ++col ) {                         // walk the 2D array by columns
            if ( front[col] == N ) continue;                                    // if the front hits row N in column col go to next column
            if ( (col > 0) && (front[col] == 0) && (front[col-1] == 0) ) break; // optimization: stop the current column iteration if the front in column col and col-1 is at row 0 (and col > 0)
            if ( m > mat[front[col]][col] ) {                                   // check 2D array for value smaller than m
                m = mat[front[col]][col];                                       // update m
                f = col;                                                        // set f for updating front but don't update front yet because another smaller value might be found
            }
        }
        arr[n] = m;                                                             // set value in 1D array
        front[f]++;                                                             // update front
    }

    for ( auto& i : arr )                                                       // print sorted 1D array
        cout << i << " ";
    cout << endl;
    
    return 0;
}

Solutions with complexity of \(\mathcal{O}(N^2)\log(N)\) are achieved by maintaining the front values in a priority queue. This is the same as the merge step of mergesort.

Simply adding all values of the 2D array into a min heap and extracting them of the top is also \(\mathcal{O}(N^2)\log(N)\) (as \(\mathcal{O}(N^2)\log(N^2) = \mathcal{O}(N^2)2\log(N) = \mathcal{O}(N^2)\log(N)\)). Adding the values to the heap following diagonals from the largest number (bottom right) to the smallest number (top left) will reduce the bubble down time.

The restrict keyword in C programming

The restrict keyword tells the compiler that for the lifetime of the respective pointer you will access the object pointed to only through this pointer (and pointers derived from it by means of pointer arithmetics). This helps the compiler to generate optimized code as demonstrated in the Wikipedia page on ‘restrict’.

In the descriptions of restrict, you will usually read the wording ‘you intend to access …’. However, as far as I understood, the result is undefined if you violate this intention. This is well described in the article ‘Demystifying The Restrict Keyword’ by Mike Acton. Background information on strict aliasing can be found in the article ‘Understanding Strict Aliasing’ by the same author.

restrict was introduced in the C99 standard (C99 on Wikipedia). Regarding GCC restrict was implemented since version 3.0 (or 3.1… doesn’t really matter anymore, I guess) but it makes good use of its optimization potential since 4.5. In GCC you can make use of restrict also if you do not (or do not want to) use -std=c99. This requires using the syntax __restrict__ (apparently __restrict works as well).

It is implemented in the Intel C compiler, where you need to pass any of the options /Qrestrict (-restrict) or /Qc99 (-c99) (see also this).

The MS compiler does not support C99, however, since version 2010 of MSVC it supports restrict using the syntax __restrict.

Most importantly, restrict can make large differences regarding code run time!