Class Sorts

#include<stdio.h>
#include<stack>
#include<math.h>
#include<time.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<iomanip>
#include<vector>
#include<map>
#include<cassert>
#include<queue>
#include <tuple>

using namespace std;

typedef long long li;
typedef long double ld;

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define pb push_back
#define mp make_pair
#define shek_shek _DEBUG
#define all(v) v.begin(),v.end()
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795

const int N = 50001;

template <typename T> class Sort {
public:
    virtual void sort(T* t_array, int array_size) = 0;
    virtual const string get_name() = 0;
};

template <typename T> class StdSort {
public:
    void sort(T* sort_array, int sort_array_size) {
        std::sort(sort_array, sort_array + sort_array_size);
    }

    void get_name () {
        return "StdSort";
    }
};

template <typename T> class HeapSort  {
private:

    T* t_array;
    int array_size;

    void heapify (int i) {
        while (2 * i + 1 < array_size) {
            int j = 2 * i + 1;
            if (j + 1 < array_size && t_array[j + 1] > t_array[j])
                j++;
            if (t_array[i] >= t_array[j])
                break;
            swap(t_array[i], t_array[j]);
            i = j;
        }
    }

    void heapSort () {
        for (int i = array_size - 1; i >= 0; i--)
            heapify(i);
        while (array_size > 1) {
            swap(t_array[0], t_array[array_size - 1]);
            array_size--;
            heapify(0);
        }
    }
public:
    void sort(T* sort_array, int sort_array_size) {
        this->t_array = sort_array;
        this->array_size = sort_array_size;
        heapSort();
    }

    string get_name() {
        return "HeapSort";
    }
};

template <typename T> class MergeSort {
private:

    T* a;
    int array_size;
    T* b;

    void merge (int l1, int r1, int l2, int r2) {
        printf("%s%d%s%d%s%d%s%d%s", "merging segments [", l1 + 1, ", ", r1 + 1, "] and [", l2 + 1, ", ", r2 + 1, "]\n");
        int i = l1,j = l2, k = l1;
        while (i <= r1 && j <= r2) {
            printf("%s%d%s%d\n","comparing ", a[i], " and ", a[j]);
            if (a[i] <= a[j]) {
                b[k] = a[i], i++, k++;
            } else {
                b[k] = a[j], j++, k++;
            }
        }
        while (i <= r1)
            b[k] = a[i], i++, k++;
        while (j <= r2)
            b[k] = a[j], j++, k++;
        for (int i = l1; i <= r2; i++)
            a[i] = b[i];
        printf("%s%d%s%d%s%d%s%d%s", "segments [", l1 + 1, ", ", r1 + 1, "] and [", l2 + 1, ", ", r2 + 1, "] merged\n");

    }

    void merge_sort (int l, int r) {
        printf("%s%d%s%d%s", "sorting segment [", l + 1, ", ", r + 1, "]\n");
        if (l == r) {
            printf("%s%d%s%d%s", "segment [", l + 1, ", ", r + 1, "] sorted\n");
            return;
        }
        if (l + 1 == r) {
            printf("%s%d%s%d\n","comparing ", a[l], " and ", a[r]);
            if (a[l] > a[r]) {
                swap(a[l], a[r]);
                printf("%s%d%s%d%s", "segment [", l + 1, ", ", r + 1, "] sorted\n");
                return;
            }
        }
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge(l, mid, mid + 1, r);
        printf("%s%d%s%d%s", "segment [", l + 1, ", ", r + 1, "] sorted\n");
    }

public:

    void sort (T* sort_array, int sort_array_size) {
        this->a = sort_array;
        this->array_size = sort_array_size;
        this->b = new T[sort_array_size];
        merge_sort(0, sort_array_size - 1);
    }

    string get_name () {
        return "MergeSort";
    }

};

template <typename T> class SortBenchmark {
private:
    int size;
    vector <T*> sorts;

public:

};


int n;
int a[N];

int main () {
#ifdef shek_shek
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    MergeSort <int> sortt;
    sortt.sort(a, n);
    cout << "result: ";
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}