MergeSort (iterativ)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "introprog_input_merge_sort.h"

void merge(int* array, int first, int middle, int last)
{
    int length = last - first + 1;
    int* b = (int*) calloc(length, sizeof(int));

    int k = first;
    int m = middle + 1;
    int i = 0;

    while (k <= middle && m <= last)
    {
        if (array[k] <= array[m]){
            b[i] = array[k];
            k += 1;
        }else {
            b[i] = array[m];
            m += 1;
        }
        i += 1;
    }

    while (k <= middle)
    {
        b[i] = array[k];
        k += 1;
        i += 1;
    }

    while (m <= last)
    {
        b[i] = array[m];
        m += 1;
        i += 1;
    }

    int j = 0;

    while (j < i)
    {
        array[first + j] = b[j];
        j += 1;
    }

    free(b);
}

void merge_sort(int* array, int last)
{
    int left, right, middle;

    int step = 1;
    while (step <= last){
    left = 0;
    while (left <= last-step){
        int m = left + step - 1;
        if (last <= m)
        {
            middle = last;
        }
        else middle = m;

        int r = left + 2*step - 1;
        if (last <= r)
        {
            right = last;
        }
        else right = r;

        merge(array, left, middle, right);

        left = left + 2*step;
    }
    step = step*2;
    }
}

int main (int argc, char *argv[])
{
    if (argc!=3){
        printf ("usage: %s <maximale anzahl>  <dateipfad>\n", argv[0]);
        exit(2);
    }

    char *filename = argv[2];
    int* array = (int*)malloc(atoi(argv[1]) * sizeof(int));
    int len = read_array_from_file(array, atoi(argv[1]), filename);


    printf("Eingabe:\n");
    print_array(array, len);

    merge_sort(array, len-1);

    printf("Sortiert:\n");
    print_array(array, len);

    free(array);

    return 0;
}