bottomup_mergesort.c

#define Minimum(A,B) ((A) < (B) ? (A) : (B))

static void
MergeSort(int *A, int Count, int *S)
{
    // A is the array to sort.
    // S should be a buffer of at least the same size as A, doesn't have to be initialized.
    for (int i = 0; i+1 < Count; i+=2)
    {
        if (A[i] > A[i+1])
        {
            int Temp = A[i];
            A[i] = A[i+1];
            A[i+1] = Temp;
        }
    }
    
    int SwappedBuffers = 0;
    
    for (int SourceBucketSize = 2; (SourceBucketSize >> 1) < Count; SourceBucketSize <<= 1)
    {
        for (int BucketOffset = 0; BucketOffset < Count; BucketOffset += 2*SourceBucketSize)
        {
            // merge two separately sorted buckets of size <= SourceBucketSize
            int *Source1 = A + BucketOffset;
            int Source1Size = Minimum(SourceBucketSize, Count - BucketOffset);
            int Offset1 = 0;
            int *Source2 = A + BucketOffset + SourceBucketSize;
            int Source2Size = Minimum(SourceBucketSize, Count - BucketOffset - SourceBucketSize);
            int Offset2 = 0;
            int *Dest = S + BucketOffset;
            
            while (Offset1 < Source1Size && Offset2 < Source2Size)
            {
                if (Source1[Offset1] <= Source2[Offset2])
                    *Dest++ = Source1[Offset1++];
                else
                    *Dest++ = Source2[Offset2++];
            }
            while (Offset1 < Source1Size)
                *Dest++ = Source1[Offset1++];
            while (Offset2 < Source2Size)
                *Dest++ = Source2[Offset2++];
        }
        
        int *Temp = A;
        A = S;
        S = Temp;
        SwappedBuffers = !SwappedBuffers;
    }
    
    if (SwappedBuffers)
    {
        int *Temp = A;
        A = S;
        S = Temp;
        for (int i = 0; i < Count; ++i)
            *A++ = *S++;
    }
}

#include <stdio.h>
#define ArrayCount(Array) (sizeof(Array) / sizeof((Array)[0]))

int main(void)
{
    int A[11] = {2,2,3,0,-3,5,7,9,1,8,4};
    int S[11];
    MergeSort(A, 11, S);
    
    for (int i = 0; i < ArrayCount(A); ++i)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}