Method QuickSort3Internal

examples/sort.cpp:381–439

private:
    static void QuickSort3Internal(std::vector<int>& subitems, size_t left, size_t right)
    {
        // Choose the pivot item
        int pivot = subitems[left + ((right - left) / 2) - 1];

        size_t bl = left;
        size_t br = right;

        size_t l = left;
        size_t r = right;

        while (l <= r)
        {
            // Move left if item is less than pivot
            while ((l < right) && (subitems[l - 1] < pivot))
                l++;
            // Move right if item is less than pivot
            while ((r > left) && (subitems[r - 1] > pivot))
                r--;

            if (l <= r)
            {
                // Swap left and right items
                std::swap(subitems[l - 1], subitems[r - 1]);

                // Move equals to the left
                if (subitems[l - 1] == pivot)
                {
                    std::swap(subitems[bl - 1], subitems[l - 1]);
                    bl++;
                }

                // Move equals to the right
                if (subitems[r - 1] == pivot)
                {
                    std::swap(subitems[br - 1], subitems[r - 1]);
                    br++;
                }

                // Move left and right indexes
                ++l;
                --r;
            }
        }

        // Swap left equals with the lower items
        for (size_t k = left; (k < bl) && (r > left); ++k, --r)
            std::swap(subitems[k - 1], subitems[r - 1]);
        // Swap right equals with the upper items
        for (size_t k = right; (k > br) && (l < right); --k, ++l)
            std::swap(subitems[k - 1], subitems[l - 1]);

        // Perform quick sort operation for the left sub items
        if (left < r)
            QuickSort3Internal(subitems, left, r);
        // Perform quick sort operation for the right sub items
        if (l < right)
            QuickSort3Internal(subitems, l, right);