17_01_mergesort.cpp

#include <iostream>
using namespace std;


template <typename T>
void merge(T* arr, const size_t& start, const size_t& mid, const size_t& end){

    size_t l_size = mid - start + 1;
    size_t r_size = end - mid;
    
    T* l_arr = new T[l_size];
    T* r_arr = new T[r_size];

    for(size_t i = 0; i < l_size; i++)
        l_arr[i] = arr[i + start];
        
    for(size_t i = 0; i < r_size; i++)
        r_arr[i] = arr[i + mid + 1];

    size_t l_i = 0;
    size_t r_i = 0;
    size_t arr_i = start;

    while(l_i < l_size && r_i < r_size){
        if(l_arr[l_i] < r_arr[r_i])
            arr[arr_i++] = l_arr[l_i++];
        else
            arr[arr_i++] = r_arr[r_i++];
    }

    while(l_i < l_size)
        arr[arr_i++] = l_arr[l_i++];

    while(r_i < r_size)
        arr[arr_i++] = r_arr[r_i++];

    delete l_arr;
    delete r_arr;

}


template <typename T>
void mergesort(T* arr, const size_t& start, const size_t& end){ 
    if(start >= end)
        return;
    size_t mid = (start + end) / 2;
    mergesort(arr, start, mid);
    mergesort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}


template <typename T>
void mergesort(T* arr, const size_t& size){  //void mergesort(T* arr, const size_t& size, int pos = 0){ ????? PERCHE NO ??????
    mergesort(arr, 0, size-1);
}


int main(){
    size_t size = 6;
    int arr[size] = {2,1,4,7,0,3};
    mergesort(arr, size);
    for(auto k : arr) cout << k << " ";
    cout << endl;
    return 0;
}