非再帰マージソート

merge.c

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

typedef struct stack_element
{
    int64_t *ptr;
    size_t length;
    int8_t state;
} stack_element_t;

stack_element_t make_stack_element(int64_t *ptr, size_t length, int8_t state)
{
    return (stack_element_t){ptr, length, state};
}

enum
{
    SPLIT,
    MERGE,
};

void sort(int64_t *ary, size_t N)
{
    // 3*log_2(x) < max(x,12)
    stack_element_t *stack = malloc(sizeof(stack_element_t) * ((N < 16) ? 16 : N));
    int64_t *buf = malloc(sizeof(int64_t) * N);
    size_t depth = 0;
    stack[depth++] = make_stack_element(ary, N, SPLIT);
    while (depth)
    {
        stack_element_t current = stack[--depth];
        size_t h = current.length / 2;
        switch (current.state)
        {
        case SPLIT:
            stack[depth++] = make_stack_element(current.ptr, current.length, MERGE);
            if (2 <= current.length)
            {

                stack[depth++] = make_stack_element(current.ptr, h, SPLIT);
                stack[depth++] = make_stack_element(current.ptr + h, current.length - h, SPLIT);
            }
            break;
        case MERGE:
            for (size_t i = 0; i < h; i++)
                buf[i] = current.ptr[i];
            size_t lhs = 0, rhs = h;
            for (size_t i = 0; i < current.length; i++)
            {
                if (lhs < h && rhs < current.length)
                    current.ptr[i] = (buf[lhs] < current.ptr[rhs]) ? buf[lhs++] : current.ptr[rhs++];
                else
                    current.ptr[i] = (lhs < h) ? buf[lhs++] : current.ptr[rhs++];
            }
            break;
        default:
            exit(1);
            break;
        }
    }
    free(stack);
    free(buf);
}

int main(int argc, char const *argv[])
{
    if (argc < 2)
    {
        puts("usage: ./merge 10");
        exit(1);
    }
    size_t N = atoll(argv[1]);
    int64_t *ary = malloc(sizeof(int64_t) * N);
    srand(time(NULL));
    for (size_t i = 0; i < N; i++)
    {
        ary[i] = rand() % N;
    }

    for (size_t i = 0; i < N; i++)
    {
        printf("%ld\t", ary[i]);
    }
    putchar('\n');

    sort(ary, N);

    for (size_t i = 0; i < N; i++)
    {
        printf("%ld\t", ary[i]);
    }
    putchar('\n');

    free(ary);

    return 0;
}