merge_sort.c

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

#define CUTOFF 8

/**
 * sort elements in range array[begin, ..., end],
 * both edge are closed.
 */
void insert_sort(int array[], int begin, int end) 
{
    for (int i=begin+1; i<=end; ++i) {
        int j=i, t=array[i];
        for (; j>begin && array[j-1]>t; --j) {
            array[j] = array[j-1];
        }   
        array[j] = t;
    }   
}

void merge(int array[], int begin, int mid, int end, int auxiliary[])
{
    int i = begin, j = mid + 1, k = begin;
    while (i<=mid && j<=end) {
        int sign = unsigned(array[i]-array[j])>>31;
        auxiliary[k++] = sign*array[i] + (1-sign)*array[j];
        i += sign;
        j += 1-sign;
    }   
    while (i <= mid) { auxiliary[k++] = array[i++]; }
    while (j <= end) { auxiliary[k++] = array[j++]; }
}

/**
 * non-recursive process, ping-pong buffer
 */
void merge_sort(int array[], int len)
{
    int auxiliary[len];
    int m=0, n=m+CUTOFF;
    while (n < len) {
        insert_sort(array, m, n-1);
        m += CUTOFF;
        n += CUTOFF;
    }
    if (m < len-1) { insert_sort(array, m, len-1); }
    if (len <= CUTOFF) { return; }

    int span=CUTOFF, range=0;
    while (1) {
        // ping
        range = span << 1;
        int i = 0;
        for (; i+range<len; i+=range) {
            merge(array, i, i+span-1, i+range-1, auxiliary);
        }
        if (i < len-span) {
            merge(array, i, i+span-1, len-1, auxiliary);
        } else {
            for (int j=i; j<len; ++j) { auxiliary[j] = array[j]; }
        }
        // [notice] under this case: copy from auxiliary to array.
        if (range >= len) {
            for (int k=0; k<len; ++k) {
                array[k] = auxiliary[k];
            }
            break;
        }
        span = range;

        // pong
        range = span << 1;
        i = 0;
        for (; i+range<len; i+=range) {
            merge(auxiliary, i, i+span-1, i+range-1, array);
        }
         if (i < len-span) {
            merge(auxiliary, i, i+span-1, len-1, array);
        } else {
            for (int j=i; j<len; ++j) { array[j] = auxiliary[j]; }
        }
        // [notice] under this case: juse break out, array is sorted.
        if (range >= len) { break; }
        span = range;
    }
}

int main()
{
    srand(time(0));
    const int arrsize = 1000 * 1000;
    int array[arrsize];
    for (int i=0; i<arrsize; ++i) {
        array[i] = rand();
    }
    merge_sort(array, arrsize);
    /*
    for (int i = 0; i < arrsize-1; ++i) {
        if (array[i] > array[i+1]) {
            printf("Failed: at %d, value: %d\n", i, array[i]);
        }
    }
    */
    return 0;
}