#include <stdio.h>                                                                                                                                                                                                                           
#include <stdlib.h>                                                                                                                                                                                                                          
#include <string.h>                                                                                                                                                                                                                          
                                                                                                                                                                                                                                             
int deep = 0;                                                                                                                                                                                                                                
                                                                                                                                                                                                                                             
void print_array(char *a, int count)
{
        for(int i = 0; i<count; i++)
        {
                printf("A[%d] = %c, ", i, a[i]);
        }
        printf("\n");
}

void print_indent()
{
        for(int i = 0; i<deep; i++) printf("    ");
}

void merge(char *A, int left, int middle, int right)
{
        int i,j,n1,n2;
        n1 = middle-left;
        n2 = right-middle+1;
        print_indent();
        printf("merge A[%d] - A[%d] with A[%d] - A[%d]\n", left, middle-1, middle, right);
        char *L = (char *)malloc(sizeof(char)*n1);
        char *R = (char *)malloc(sizeof(char)*n2);
        for(i=0; i<n1; i++) L[i]=A[left+i];
        for(j=0; j<n2; j++) R[j]=A[middle+j];
        L[i]=127; R[j]=127;
        i = 0; j = 0;
        for(int k = left; k<=right; k++)
        {
                print_indent();
                if(L[i] <= R[j])
                {
                        A[k] = L[i];
                        printf("A[%d]=L[%d]=%c\n", k, i, L[i]);
                        i++;
                }
                else
                {
                        A[k] = R[j];
                        printf("A[%d]=R[%d]=%c\n", k, j, R[j]);
                        j++;
                }
        }
}

void mergesort(char *A, int left, int right)
{
        deep++;
        print_indent();
        printf("mergesort: A[%d] - A[%d]\n", left, right);
        int middle;
        if(left<right)
        {
                middle = (left+right)/2;
                mergesort(A, left, middle);
                mergesort(A, middle+1, right);
                merge(A, left, middle+1, right);
        }
        deep--;
}

int main(int argc, char **argv)
{
        char a[] = {0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39}; 
        int count = sizeof(a)/sizeof(a[0]);
        //char *a = argv[1];
        //int count = strlen(argv[1]);
        print_array(a, count);
        mergesort(a, 0, count-1);
        print_array(a, count);
        return 0;
}