Sort K-Sorted Array

• Time : O(nlogk)
• Space : O(1)

c++

vector<int> sortKSortedArray(vector<int> array, int k) {
    array.push_back(INT_MAX);
    int n = array.size();
    k = min(k, n - 1);
    for(int i = 0, j = k + 1; j <= n; j++,i++) {
        sort(begin(array) + i, begin(array) + j);
    }
    array.pop_back();
    return array;
}