quadratic sort

quadratic.cpp

int quadratic(int size) {
    int num_solid = 0;
    // gas means "infinity"
    int gas = size + 1;
    int comparison_count = 0;
    std::vector<int> indices(size);
    std::vector<int> values(size);
    // indices are 0, 1, ..., size
    // values are all infinite
    for (int i = 0; i < size; ++i) {
        indices[i] = i;
        values[i] = gas;
    }
    // Enforce uniform input distribution!
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(indices.begin(), indices.end(), g);
    sort(indices.begin(), indices.end(), [&](int x, int y) {
        comparison_count += 1;
        // If both infinite, set left.
        // Otherwise gas is always more
        if (values[x] == gas && values[y] == gas) {
            values[x] = num_solid++;
            return true;
        } else if (values[x] == gas) {
            return false;
        } else if (values[y] == gas) {
            return true;
        } else {
            return values[x] < values[y];
        }
    });
    return comparison_count;
}