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;
            }
        }
    }
}