C++ equivalent of C# Array.Sort

Question

If it exists, what would be the C++ equivalent of the C# Array.Sort<TKey,TValue>(TKey[], TValue[], Int32, Int32)? I looked at the source code of the C# function but i could not work it out.

Advice -- do not write a C++ program using C# or any other language as a model. All you will end up with is a program that has bugs, leaks memory, is inefficient, or just plain looks weird to another C++ programmer. — PaulMcKenzie, Jun 12 '20 at 12:25
Isn't there in C++ some kind of dictionary that can be iterated by sorted keys ? Extracting the values from a dict sorted by keys would solve your issue — Cid, Jun 12 '20 at 12:31
Maybe you could use something like [std::partial_sort](https://en.cppreference.com/w/cpp/algorithm/partial_sort) to achieve whatever you are trying to do? — vonludi, Jun 12 '20 at 12:33
I’m guessing it’s a duplicate of this: https://stackoverflow.com/a/236199/1968 — Konrad Rudolph, Jun 12 '20 at 12:33
Have you looked at std::sort ? https://en.cppreference.com/w/cpp/algorithm/sort — Dave Doknjas, Jun 12 '20 at 14:06

bipll · Answer 1 · 2020-06-12T13:03:15.497

The doc link you provided says nothing about algorithm complexity (unsurprisingly, taking into account how good is that company with providing necessary information). In general, this does not look doable without at least an extra O(N) space. Konrad's solution linked in comments is perhaps the cheapest one, but if elements of your arrays are small and trivial, you can sort them by e.g. simply putting them in a map:

std::multimap<TKey, TValue> items;
for(std::size_t i{}; i < keys.size(); ++i) {
    items.emplace(std::move(keys[i]), std::move(values[i]));
}

std::size_t i{};
for(auto &&kv: items) {
    keys[i] = kv.first;
    keys[i] = std::move(kv.second);
    ++i;
}

(Two one-liner std::transforms can be used in place of the second loop, one copies keys, the other values.)

Or an array instead of a map:

std::vector<std::pair<TKey, TValue>> items(keys.size());
std::transform(
        std::make_move_iterator(keys.begin()),
        std::make_move_iterator(keys.end()),
        std::make_move_iterator(values.begin()),
        items.begin(),
        (auto &&k, auto &&v) { return std::pair{std::move(k), std::move(v); });

std::sort(items.begin(), items.end(), [](auto const &l, auto const &r) {
        return l.first < r.first;
});
// Now copy them back, like above.

Zip iterator could prove useful here, but it's not in the STL so only library-level solutions.

Complexity is known *"If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm. If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm. Otherwise, it uses a Quicksort algorithm."* That's from the docs, in the part *Remarks* — Cid, Jun 12 '20 at 18:18
and the source code is available so it's also easy to check the complexity https://referencesource.microsoft.com/#mscorlib/system/array.cs, https://github.com/microsoft/referencesource/blob/master/mscorlib/system/array.cs — phuclv, May 24 '22 at 04:01

score 0 · Accepted Answer · answered May 23 '22 at 23:37

I ended up using the following code based on the .NET code. The main function is IntrospectiveSort:

    static void IntrospectiveSort(int keys[], double items[], int left, int right) {

        // Make sure left != right in your own code.
        _ASSERTE(keys != NULL && left < right);

        int length = right - left + 1;

        if (length < 2)
            return;

        IntroSort(keys, items, left, right, 2 * FloorLog2(length));
    }
    static const int introsortSizeThreshold = 16;
    static int FloorLog2(int n)
    {
        int result = 0;
        while (n >= 1)
        {
            result++;
            n = n / 2;
        }
        return result;
    }
    inline static void SwapIfGreaterWithItems(int keys[], double items[], int a, int b) {
        if (a != b) {
            if (keys[a] > keys[b]) {
                int key = keys[a];
                keys[a] = keys[b];
                keys[b] = key;
                if (items != NULL) {
                    double item = items[a];
                    items[a] = items[b];
                    items[b] = item;
                }
            }
        }
    }
    static void IntroSort(int keys[], double items[], int lo, int hi, int depthLimit)
    {
        while (hi > lo)
        {
            int partitionSize = hi - lo + 1;
            if (partitionSize <= introsortSizeThreshold)
            {
                if (partitionSize == 1)
                {
                    return;
                }
                if (partitionSize == 2)
                {
                    SwapIfGreaterWithItems(keys, items, lo, hi);
                    return;
                }
                if (partitionSize == 3)
                {
                    SwapIfGreaterWithItems(keys, items, lo, hi - 1);
                    SwapIfGreaterWithItems(keys, items, lo, hi);
                    SwapIfGreaterWithItems(keys, items, hi - 1, hi);
                    return;
                }

                InsertionSort(keys, items, lo, hi);
                return;
            }

            if (depthLimit == 0)
            {
                Heapsort(keys, items, lo, hi);
                return;
            }
            depthLimit--;

            int p = PickPivotAndPartition(keys, items, lo, hi);
            IntroSort(keys, items, p + 1, hi, depthLimit);
            hi = p - 1;
        }
        return;
    }
    static void Swap(int keys[], double items[], int i, int j)
    {
        int t = keys[i];
        keys[i] = keys[j];
        keys[j] = t;

        if (items != NULL)
        {
            double item = items[i];
            items[i] = items[j];
            items[j] = item;
        }
    }
    static int PickPivotAndPartition(int keys[], double items[], int lo, int hi)
    {
        // Compute median-of-three.  But also partition them, since we've done the comparison.
        int mid = lo + (hi - lo) / 2;

        // Sort lo, mid and hi appropriately, then pick mid as the pivot.
        SwapIfGreaterWithItems(keys, items, lo, mid);
        SwapIfGreaterWithItems(keys, items, lo, hi);
        SwapIfGreaterWithItems(keys, items, mid, hi);

        int pivot = keys[mid];
        Swap(keys, items, mid, hi - 1);

        int left = lo, right = hi - 1;  // We already partitioned lo and hi and put the pivot in hi - 1.  And we pre-increment & decrement below.

        while (left < right)
        {
            while (left < (hi - 1) && keys[++left] < pivot);
            while (right > lo && pivot < keys[--right]);

            if ((left >= right))
                break;

            Swap(keys, items, left, right);
        }

        // Put pivot in the right location.
        Swap(keys, items, left, (hi - 1));
        return left;
    }
    static void Heapsort(int keys[], double items[], int lo, int hi)
    {
        int n = hi - lo + 1;
        for (int i = n / 2; i >= 1; i = i - 1)
        {
            DownHeap(keys, items, i, n, lo);
        }
        for (int i = n; i > 1; i = i - 1)
        {
            Swap(keys, items, lo, lo + i - 1);
            DownHeap(keys, items, 1, i - 1, lo);
        }
    }
    static void DownHeap(int keys[], double items[], int i, int n, int lo)
    {
        int d = keys[lo + i - 1];
        double di = (items != NULL) ? items[lo + i - 1] : NULL;
        int child;

        while (i <= n / 2)
        {
            child = 2 * i;
            if (child < n && keys[lo + child - 1] < keys[lo + child])
            {
                child++;
            }
            if (!(d < keys[lo + child - 1]))
                break;

            keys[lo + i - 1] = keys[lo + child - 1];
            if (items != NULL)
                items[lo + i - 1] = items[lo + child - 1];
            i = child;
        }
        keys[lo + i - 1] = d;
        if (items != NULL)
            items[lo + i - 1] = di;
    }
    static void InsertionSort(int keys[], double items[], int lo, int hi)
    {
        int i, j;
        int t;
        double ti = NULL;
        for (i = lo; i < hi; i++)
        {
            j = i;
            t = keys[i + 1];
            if (items != NULL)
                ti = items[i + 1];
            while (j >= lo && t < keys[j])
            {
                keys[j + 1] = keys[j];
                if (items != NULL)
                    items[j + 1] = items[j];
                j--;
            }
            keys[j + 1] = t;
            if (items != NULL)
                items[j + 1] = ti;
        }
    }

C++ equivalent of C# Array.Sort

2 Answers2