#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;

// =============================================
// KONFIGURASI — ubah nilai di sini
// =============================================
const int DATA_SIZE = 10000;  // jumlah elemen

// Pilih kondisi: "avg", "best", atau "worst"
const string CASE = "worst";
// =============================================

void mergeHelp(vector<int>& a, int l, int mid, int r) {
    int n1 = mid - l + 1, n2 = r - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

void mergeRec(vector<int>& a, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeRec(a, l, m);
        mergeRec(a, m + 1, r);
        mergeHelp(a, l, m, r);
    }
}

void mergeSort(vector<int>& a) {
    mergeRec(a, 0, (int)a.size() - 1);
}

vector<int> generateData(int n, const string& caseType) {
    vector<int> data(n);

    if (caseType == "best") {
        // Best case: sudah terurut ascending
        for (int i = 0; i < n; i++) data[i] = i + 1;

    } else if (caseType == "worst") {
        // Worst case: urutan terbalik (descending)
        for (int i = 0; i < n; i++) data[i] = n - i;

    } else {
        // Average case: acak (random shuffle)
        for (int i = 0; i < n; i++) data[i] = i + 1;
        mt19937 rng(42);
        shuffle(data.begin(), data.end(), rng);
    }

    return data;
}

int main() {
    vector<int> data = generateData(DATA_SIZE, CASE);

    auto start = chrono::high_resolution_clock::now();
    mergeSort(data);
    auto end = chrono::high_resolution_clock::now();

    double ms = chrono::duration<double, milli>(end - start).count();

    cout << "Case     : " << CASE << endl;
    cout << "Size     : " << DATA_SIZE << endl;
    cout << "Waktu    : " << ms << " ms" << endl;

    return 0;
}