Merge sort (C implemetation)

merge_sort.c

/**
 * Merge sort
 *
 * @link https://en.wikipedia.org/wiki/Merge_sort
 *
 * I went from the other side, using the features of the C with memory.
 *
 * Walk through an array with step equal 2 and get slices of 2 elements. Sort the elements in each
 * slice. Get a new array. Then double step, go through the new array, yielding slices
 * of the 4 elements. In each slice sort items by comparing them from the left and right side
 * of the slice. Get the new array. Double step, slices of 8 elements, sorting them by compare each
 * element from halves of the slice. Get new array, etc.
 * 
 * For implemetation of the described algorithm I use two arrays of the same size. After each step,
 * one of them contains the current state of data to be sorted. Swap pointers to arrays and run the
 * next step of sorting.
 *
 * Usage:
 *
 *   merge [count] [seed]
 *
 * [count] - amount of elements
 * [seed] - seed for random generator.
 *
 * BTW: for a maximum possible value change the constant MAXVAL below.
 *
 * @author Vijit <[email protected]>
 * @since feb.2016
 */

#define _XOPEN_SOURCE

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define COUNT 17
#define MAXVAL 50
#define DEBUG

void sortPart(int values[], int mirror[], int left, int middle, int right);
void printArray(int values[], int count);

int main(int argc, char *argv[])
{
    int cnt = (argc > 1) ? atoi(argv[1]) : COUNT;
    if (cnt < 2) return 0;

    if (argc == 3) {
        srand48((long int) atoi(argv[2]));
    } else {
        srand48((long int) time(NULL));
    }

    int *values;
    int *mirror;
    int *swap;
    values = malloc((cnt) * sizeof(int));
    mirror = malloc((cnt) * sizeof(int));

    for (size_t i = 0; i < cnt; i++) {
        values[i] = drand48() * MAXVAL;
    }

    printf(" 0: ");
    printArray(values, cnt);

    int step = 1;
    do {
        int left = 0;
        int middle;
        int right;
        do {
            middle = left + step;
            if (middle >= cnt) {
                middle = cnt - 1;
            }

            right = middle + step;
            if (right > cnt) {
                right = cnt;
            }

            sortPart(values, mirror, left, middle, right);

            left = right;
       } while (right < cnt);

        swap = values;
        values = mirror;
        mirror = swap;

        #ifdef DEBUG
        printf("%2i: ", step);
        printArray(values, cnt);
        #endif

        step <<= 1;
    } while (step < cnt);

    printf("\nFinal\n");
    printArray(values, cnt);

    free(values);
    free(mirror);

    return 0;
}

/**
 * Slice of array "values" is divided into two intervals: [left, middle) and [middle, right).
 * Compare each element of first one with each element of another gap and build mutual sorted array.
 *
 * @param int values[] array with source data
 * @param int mirror[] array to store changes
 * @param int left     left index of slice
 * @param int middle   middle index of slice
 * @param int right    right index if slice
 * @return void
 */
void sortPart(int values[], int mirror[], int left, int middle, int right)
{
    int
        i = left,
        j = middle,
        k = left;

    int v1, v2;

    do {
        v1 = values[i];
        v2 = values[j];

        if (v1 >= v2) {
            mirror[k] = v2;
            j++;
        } else {
            mirror[k] = v1;
            i++;
        }

        k++;
    } while (i < middle && j < right);

    // One (or maybe both) of the next cycles wouldn't fired up, because previous cycle has emptied
    // intervals as possible. At least one interval is empty now.

    for (; i < middle; i++) {
        mirror[k] = values[i];
        k++;
    }

    for (; j < right; j++) {
        mirror[k] = values[j];
        k++;
    }
}

/**
 * Print an array into string.
 *
 * @param int values[] array
 * @param int count amount of elements
 * @return void
 */
void printArray(int values[], int count)
{
    for (size_t i = 0; i < count; i++) {
        printf("%2i ", values[i]);
    }
    printf("\n");
}