#ifndef CHATGPT_QS_H
#define CHATGPT_QS_H

std::vector<uint32_t> gpt_quicksort(const std::vector<uint32_t> &arr) {
    if (arr.size() <= 1) {
        return arr;
    }

    uint32_t pivot = arr[arr.size() / 2];
    std::vector<uint32_t> left;
    std::vector<uint32_t> middle;
    std::vector<uint32_t> right;

    for (uint32_t x : arr) {
        if (x < pivot) {
            left.push_back(x);
        } else if (x == pivot) {
            middle.push_back(x);
        } else {
            right.push_back(x);
        }
    }

    std::vector<uint32_t> sorted_left = gpt_quicksort(left);
    std::vector<uint32_t> sorted_right = gpt_quicksort(right);

    // Concatenate sorted_left + middle + sorted_right
    std::vector<uint32_t> result;
    result.reserve(sorted_left.size() + middle.size() + sorted_right.size());
    result.insert(result.end(), sorted_left.begin(), sorted_left.end());
    result.insert(result.end(), middle.begin(), middle.end());
    result.insert(result.end(), sorted_right.begin(), sorted_right.end());

    return result;
}

#endif // CHATGPT_QS_H