#include <iostream>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>
using namespace std;
int d [100];

void mergeSort(int p, int k);
void merge_ (int p, int q, int k);
int main() {
    int i;
    int N = 100;
    srand((unsigned)time(NULL));
    for(i = 0; i < N; i++) d[i] = rand() % 100;
    for(i = 0; i < N; i++) cout << setw(4) << d[i];
    cout << endl;
    //Sortujemy
    mergeSort(0, 99);
    // Wyświetlamy wynik sortowania
    cout << "Po sortowaniu:\n\n";
    for(i = 0; i < N; i++) cout << setw(4) << d[i];
    cout << endl;
    return 0;
}
void mergeSort(int p, int k) {
    for (int i=0; i<100; i++) {
        cout << d[i] << "\n";
    }
    if (p<k) {
        int q = p+k;
        q = q/2;
        mergeSort(p, q);
        mergeSort(q+1, k);
        merge_(p, q, k);
    }
}
void merge_ (int p, int q, int r) {
    int n1 = q-p;
    int n2 = r-q;
    int* L = new int [n1];
    int* R = new int [n2];
    for (int i=0; i<n1; i++) {
        L[i] = d[p+i];
        //cout << d[p+i] << "\n";
        //cout << L[i] << "\n";
    }
    for (int i=0; i<n2; i++) {
        R[i] = d[q+i];
    }
    int i = 0;
    int j = 0;
    for (int k=0; k<=r; k++) {
        if (L[i]<=R[j]) {
            d[k]=L[i];
            i=i+1;
        }
        else {
            d[k]=R[j];
            j=j+1;
        }
    }
}