//input matrix must be of type CV_8UC1
void MatrixSort(Mat matrix)
{
    //matrix that stores the indices from sortIdx
    Mat matrixRowIndices(matrix.rows, matrix.cols, CV_8UC1);
    sortIdx(matrix, matrixRowIndices, SORT_EVERY_ROW + SORT_ASCENDING);

    //reconstruate the sorted matrix from the row indices
    Mat sortedRowmatrix(matrix.rows, matrix.cols, CV_8UC1);
    for (int row = 0; row < matrixRowIndices.rows; row++)
    {
        for (int col = 0; col < matrixRowIndices.cols; col++)
        {
            int pukIDIndex = matrixRowIndices.at<int>(row, col);
            int distance = matrix.at<uchar>(row, pukIDIndex);
            sortedRowmatrix.at<uchar>(row, col) = distance;
        }
    }
    cout << "sorted row indices = " << endl << matrixRowIndices << endl << endl;
    cout << "sorted row matrix = " << endl << sortedRowmatrix << endl << endl;

    //sortIdx on the columns
    Mat matrixColIndices(matrix.rows, matrix.cols, CV_8UC1);
    sortIdx(sortedRowmatrix, matrixColIndices, SORT_EVERY_COLUMN + SORT_ASCENDING);
    cout << "sorted col indices= " << endl << matrixColIndices << endl << endl;

    //reconstruate the rows and columns sorted matrix
    Mat sortedColmatrix(matrix.rows, matrix.cols, CV_8UC1);
    for (int row = 0; row < sortedColmatrix.rows; row++)
    {
        for (int col = 0; col < sortedColmatrix.cols; col++)
        {
            //sort rows gives back the indexes of columns in the matrix before sorting.
            int pukIDIndex = matrixColIndices.at<int>(row, col);

            //sort columns gives back the indexes of rows in the matrix before sorting.
            int pukIDIndex2 = matrixRowIndices.at<int>(row, col);

            int distance = matrix.at<uchar>(pukIDIndex, pukIDIndex2);
            sortedColmatrix.at<uchar>(row, col) = distance;
        }
    }

    cout << "sorted matrix indices = " << endl << sortedColmatrix << endl << endl;

    //Below is the correctly sorted matrix with the normal sort algorithm. This works (but does not gives the indices I require.)
    Mat sortedDistanceMat(matrix.rows, matrix.cols, CV_8UC1);
    cv::sort(matrix, sortedDistanceMat, SORT_EVERY_ROW + SORT_ASCENDING);
    cv::sort(sortedDistanceMat, sortedDistanceMat, SORT_EVERY_COLUMN + SORT_ASCENDING);

    cout << "correctly sorted matrix = " << endl << sortedDistanceMat << endl << endl;
}