ID    Значение
1    2
2    3
1    2
3    5

ID    Значение
1    2
2    3
3    2
4    5

void Matrix::QuickSort(Matrix matrix, int * idx, int first, int last)
{
    double p = *matrix((last - first) / 2 + first);
    double temp;
    int idxTemp;
    int i = first;
    int j = last;
    while (i <= j)
    {
        while (*matrix(i) < p && i <= last) ++i;
        while (*matrix(j) > p && j >= first) --j;
        if (i <= j)
        {
            temp = *matrix(i);
            idxTemp = idx[i - 1];
            *matrix(i) = *matrix(j);
            *matrix(j) = temp;
            idx[i - 1] = idx[j - 1];
            idx[j - 1] = idxTemp;
            ++i; --j;
        }
    }
    if (j > first) QuickSort(matrix, idx, first, j);
    if (i < last) QuickSort(matrix, idx, i, last);
}

void Matrix::QuickSort(Matrix matrix, int * idx, int first, int last)
{
//...
        while (*matrix(i) < p && i <= last) ++i;
        while (*matrix(j) > p && j >= first) --j;
//...
}

G>>Есть массив значений, каждое значение имеет свой ID. Нужно отсортировать этот массив так, чтобы одинаковые значения были отсортированы по ID. Сейчас я сортирую 2 раза, сперва массив, потом ID. Но по времени не укладываюсь в рамки

G>Мда, а причина то оказывается не в том, что сортировка в 2 прохода Тупо все циклы занимают 50% времени, 45% на перемещение данных и 5% на досортировку ID.

    while (i <= j)
    {
        while (*matrix(i) < p && i <= last) ++i;
        while (*matrix(j) > p && j >= first) --j;
        if (i <= j)
        {
            temp = *matrix(i);
            idxTemp = idx[i - 1];
            *matrix(i) = *matrix(j);
            *matrix(j) = temp;
            idx[i - 1] = idx[j - 1];
            idx[j - 1] = idxTemp;
            ++i; --j;
        }
    }

void Matrix::Sort(Matrix matrix, Matrix * sortedMatrix, int* idx)
{
    sortedMatrix->Copy(&matrix);//входную матрицу менять нельзя

    if (sortedMatrix->RowsNumber() != 1 && sortedMatrix->ColumnsNumber() != 1)//если не вектор
    {
        sortedMatrix = &sortedMatrix->ToVector();
    }

    for (int i = 1; i <= sortedMatrix->RowsNumber(); i++)
    {
        idx[i - 1] = i;
    }

    int rows = sortedMatrix->RowsNumber();//длина вектора

    QuickSort(*sortedMatrix, idx, 1, rows);
    QuickSortIndexes(*sortedMatrix, idx);//тут время выполнения 0.5с
}
void Matrix::QuickSort(Matrix matrix, int * idx, int first, int last)
{
    double p = *matrix((last - first) / 2 + first);
    double temp;
    int idxTemp;
    int i = first;
    int j = last;
    while (i <= j)
    {
        while (*matrix(i) < p && i <= last) ++i;
        while (*matrix(j) > p && j >= first) --j;
        if (i <= j)
        {
            temp = *matrix(i);
            idxTemp = idx[i - 1];
            *matrix(i) = *matrix(j);
            *matrix(j) = temp;
            idx[i - 1] = idx[j - 1];
            idx[j - 1] = idxTemp;
            ++i; --j;
        }
    }
    if (j > first) QuickSort(matrix, idx, first, j);
    if (i < last) QuickSort(matrix, idx, i, last);
}

void Matrix::QuickSortIndexes(Matrix matrix, int * idx)
{
    int first;
    int last;
    for (int i = 1; i <= matrix.RowsNumber(); i++)
    {
        first = i - 1;
        if (i != matrix.RowsNumber())
        {
            while (*matrix(i) == *matrix(i + 1))
            {
                i++;
                if (i == matrix.RowsNumber())
                    break;
            }
            last = i - 1;
            QuickSort(idx, first, last);
        }
    }
}

        vector<pair<double, int>> values;
    vector<pair<double, int>>::iterator it;
    values.resize(sortedMatrix->RowsNumber());
    
    int i = 1;
    for (it = values.begin(); it != values.end(); it++, i++)
        {
        (*it).first = *(*sortedMatrix)(i);
        (*it).second = i - 1;
        }
    stable_sort(values.begin(), values.end());

G>        vector<pair<double, int>> values;
G>    vector<pair<double, int>>::iterator it;
G>    values.resize(sortedMatrix->RowsNumber());
    
G>    int i = 1;
G>    for (it = values.begin(); it != values.end(); it++, i++)
G>        {
G>        (*it).first = *(*sortedMatrix)(i);
G>        (*it).second = i - 1;
G>        }
G>    stable_sort(values.begin(), values.end());
G>

vector<pair<double, int>> values;
values.reserve(sortedMatrix->RowsNumber());

for(int i = 1, iE = sortedMatrix->RowsNumber(); i <= iE; ++i)
{
   values.push_back( std::make_pair( *(*sortedMatrix)(i), i-1) );
}