#include "mergesort.h"

MergeSort::MergeSort(QObject *parent):
    IAlgo(parent)
{

}

QString MergeSort::name()
{
    return "Merge Sort";
}

void MergeSort::run()
{
    _run_time = 0;
    QVector<int> &data = _data->GetData();
    sort(data, 0, data.size() - 1);
}

// closed interval
void MergeSort::sort(QVector<int> &data, int left, int right)
{
    if(right - left > 0){
        int mid = (right - left)/2 + left;
        sort(data, left, mid);
        sort(data, mid + 1, right);
        merge(data, left, mid, right);
    }
}

// closed interval
void MergeSort::merge(QVector<int> &data, int left, int mid, int right)
{
    QVector<int> data_left;
    for(int i = 0; i < mid - left + 1; ++i){
        data_left.append(data[left + i]);
        _run_time ++;
    }
    data_left.append(std::numeric_limits<int>::max());

    QVector<int> data_right;
    for(int i = 0; i < right - mid; ++i){
        data_right.append(data[mid + 1 + i]);
        _run_time ++;
    }
    data_right.append(std::numeric_limits<int>::max());

    int left_pos = 0;
    int right_pos = 0;

    for(int i = 0; i < right - left + 1; ++i){
        if(data_left[left_pos] < data_right[right_pos]){
            data[left + i] = data_left[left_pos];
            ++left_pos;
        }
        else{
            data[left + i] = data_right[right_pos];
            ++right_pos;
        }
        _run_time ++;
        _data->Refresh();
    }
}