/*-----------------------------------------------------------------------------
 *				HTBLA-Leonding
 *-----------------------------------------------------------------------------
 * Exercise Number: S06
 * Title:			Insertion sort implementation
 * Author:			Marc Tismonar
 *-----------------------------------------------------------------------------
 * Description:
 * Implements the merge sort strategy
 *-----------------------------------------------------------------------------
*/

#include "merge_sort.h"

static void merge_sort_list_merge(IntList list, IntList left, IntList right, criterion_fn criterion) {
    while (list_get_size(left) > 0 && list_get_size(right) > 0) {
        if (criterion(list_get_at(left, 0), list_get_at(right, 0))) {
            list_transfer_head(left, list);
        } else {
            list_transfer_head(right, list);
        }
    }
    list_append(list, left);
    list_append(list, right);
}

static IntList merge_sort_list_divide_merge(IntList list, IntList result, criterion_fn criterion) {
    if (list_get_size(list) <= 1) {
        list_append(result, list);
        return result;
    }

    IntList left = list_obtain(), right = list_obtain();
    IntList left_result = list_obtain(), right_result = list_obtain();

    list_split(list, left, right, list_get_size(list) / 2);
    merge_sort_list_divide_merge(left, left_result, criterion);
    merge_sort_list_divide_merge(right, right_result, criterion);
    merge_sort_list_merge(result, left_result, right_result, criterion);

    list_release(&left);
    list_release(&right);
    list_release(&left_result);
    list_release(&right_result);

    return result;
}

/**
 * Sorts the given list according to the merge sort strategy.
 * 
 * @param list The list to be sorted.
 * @param criterion The pointer to the function that implements the sorting criterion.
 * That function accepts two integer parameters and returns a boolean value.
 */
void merge_sort_list(IntList list, criterion_fn criterion) {
    IntList result = list_obtain();
    result = merge_sort_list_divide_merge(list, result, criterion);
    list_clear(list);
    list_append(list, result);
    list_release(&result);
}   

/**
 * Sorts the given array according to the merge sort strategy.
 * 
 * @param array The array to be sorted.
 * @param length The length of the array.
 * @param criterion The pointer to the function that implements the sorting criterion.
 * That function accepts two integer parameters and returns a boolean value.
 */
void merge_sort_array(int array[], int length, criterion_fn criterion) {

}