#include <iostream>
#include <vector>
#include "math.h"
using namespace std;

// Time Complexity from O(n log(n)) to O(n^2)
// Space Complexity O(log(n))
void doSort(vector<int> &items, int fst, int lst) {
    if (fst >= lst) {
        return;
    }
    int i = fst;
    int j = lst;
    int x = items[(fst + lst)/2];

    while (i < j) {
        while (items[i] < x) i++;
        while (items[j] > x) j--;
        if (i <= j) {
            int tmp = items[i];
            items[i] = items[j];
            items[j] = tmp;
            i++;
            j--;
        }
    }
    doSort(items, fst, j);
    doSort(items, i, lst);
}

vector<int> sort(vector<int> arr)
{
    int len = (int)arr.size();
    vector<int> items(arr);
    doSort(items, 0, len - 1);
    return items;
}

vector<int> items = { 4, 1, 5, 3, 2 };

vector<int>sortItems = sort(items);
// sortItems is {1, 2, 3, 4, 5}

for (int i : sortItems) cout << i << ", ";
cout << endl;

// *** simplified speed test ***

items = vector<int>(200, 0);
for (int i = 0; i < items.size(); i++) {
    items[i] = i;
}
int tmp = items[5];
items[5] = items[6];
items[6] = tmp;
int count = 100000;

time_t start = time(0);

for (int i = 0; i < count; i++) {
    sort(items);
}

long seconds = time(0) - start;

cout << seconds << " seconds";
// about 1 seconds