Envío 1570

Código

#include <vector>
#include <iostream>
using namespace std;
int partition(vector<int> &nums, int left, int right) {
    if (left >= right) {
        return left;
    }
    int mid = left + (right - left) / 2;
    int pivot = nums[right];
    int pos = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] < pivot) {
            swap(nums[i], nums[pos++]);
        }
    }
    swap(nums[right], nums[pos]);
    return pos;
}

void sort(vector<int> &nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int pos = partition(nums, left, right);
    sort(nums, left, pos - 1);
    sort(nums, pos + 1, right);
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    int left = -1;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        if (i > 0 and nums[i] < nums[i-1] and left == -1) {
            left = i - 1;
        }
    }

    sort(nums, max(left, 0), n - 1);
    for(int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}