Segment tree sorting

(If you aren't familiar with what a segment tree is then I would recommend reading https://cp-algorithms.com/data_structures/segment_tree.html )

So I came up with a cool way of sorting an array with a segment tree. I'm not sure if this has been thought of before, but if it hasn't, then it would be cool to share. I did some comparisons against other ways of sorting, and it outperformed the other ways, aside from std::sort. My implementation of the other sorting techniques could probably be improved though. So here is the general idea:

General idea

Each node of the segment tree stores two elements. It stores the minimum value of all nodes beneath it, as well as storing the index of this minimum node. Start by creating the segment tree with these elements in it, then we repeat N times : 1. Add node 1's minimum value to our sorted list. 2. Update the index of that minimum value to INT_MAX, as after adding it to the sorted array, you want to effectively remove it from the tree.

Time complexity: O(n log(n))

Implementation details

We start by constructing the array with this:

void construct(vector<int> *v) {
        for(int i = 0; i < n; i++) {
            seg[i + n] = {(*v)[i], i};
        }
        for(int i = n- 1; i> 0; i--) {
            if(seg[i * 2 + 1].first < seg[i * 2].first) {
                seg[i] = seg[i * 2 + 1];
            }else {
                seg[i] = seg[i * 2];
            }
        }
    }
}

Then for i in range(n), we find the minimum value, seg[1].first, and then set seg[1].second to INT_MAX with:

void update(int index) {
        seg[index + n].first = INT_MAX;
        for(int i = (index + n)/2; i> 0; i/=2) {
            pair<int, int> a = seg[i *2 + 1];
            pair<int, int> b = seg[i * 2];
            if(a.first < b.first) {
                seg[i] = a;
            }else {
                seg[i] = b;
            }
        }
    }
}

How did it compare to other sorting algorithms?

When I ran it on my computer for an array of size 10,000,000:

• Standard sort took 2.09876 seconds
• Segment tree sort took 3.10657 seconds
• Heap sort took 4.50604 seconds
• Merge sort took 4.61425 seconds
• Quick sort took 5.76152 seconds

Array size of 1,000,000:

• Standard sort took 0.177153 seconds
• Segment tree sort took 0.192566 seconds
• Heap sort took 0.372507 seconds
• Merge sort took 0.407037 seconds
• Quick sort took 0.529488 seconds

Array of size 100,000:

• Standard sort took 0.0153477 seconds
• Segment tree sort took 0.0158673 seconds
• Heap sort took 0.0318967 seconds
• Merge sort took 0.0390352 seconds
• Quick sort took 0.0490728 seconds

Array of size 10,000:

• Standard sort took 0.00122976 seconds
• Segment tree sort took 0.00126829 seconds
• Heap sort took 0.00270543 seconds
• Merge sort took 0.00367626 seconds
• Quick sort took 0.00454401 seconds

Even though my merge and quick sort could probably be optimized, the segment tree sort did very well, being comparable to std::sort.

Github link: https://github.com/quollcucumber/segtreesort