#include <iostream>
#include <cmath>
#include <algorithm>
#include <math.h>
#include <vector>
#include <fstream>

using namespace std;

const int N = 5;

void mySwap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

void printArray(int arr[]) {
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// =============== Quick Sort ===============
void quickSort(int A[],int left, int rigth) {
    int i = left, j = rigth;
    int pivot = A[(rigth + left)/2];

    while (i <= j) {
            printArray(A);
        while (A[i] < pivot) i++;
        while (A[j] > pivot) j--;

        if (i <= j) {
            mySwap(A[i], A[j]);
            i++;
            j--;
        }

    }

    if (left < j) quickSort(A, left, j);
    if (rigth > i) quickSort(A, i, rigth);
}

// =============== Merge Sort ===============

void myMerge(int A[], int l, int m, int r) {
    int i, j, k;
    int n1 = l-m + 1;
    int n2 = r-m;

    int L[n1], R[n2];

    for (i = 0; i < n1; ++i) {
        L[i] = A[l + i];
    }
    for (i = 0; i < n2; ++i) {
        R[i] = A[m + 1 + i];
    }

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        A[k] = L[i];
        k++;
        i++;
    }
    while (j < n2) {
        A[k] = R[j];
        j++;
    }

}

void mergeSort(int A[],int left, int rigth) {
    if (left < rigth) {
        int m = A[(rigth + left)/2];

        mergeSort(A, left, m);
        mergeSort(A, m+1, rigth);

        myMerge(A, left, m, rigth);
    }
}

int main()
{
    int a[N] = {7, 9, 5, 1, 3};

    quickSort(a, 0, N-1);
    mergeSort(a, 0, N-1);
    printArray(a);

    return 0;
}