sort

#include <stdio.h>


void print_array(int a[], int n)
{
    int i;

    for (i=0; i<n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void quick_sort(int a[], int l, int r)
{
    int i = l, j = r;
    int k = a[l];

    if (l >= r)
    {
        return;
    }

    while (i < j)
    {
        while (i < j && a[j] >= k)
        {
            j--;
        }
        if (a[j] < k)
        {
            a[i++] = a[j];
        }

        while (i < j && a[i] <= k)
        {
            i++;
        }
        if (a[i] > k)
        {
            a[j--] = a[i];
        }
    }
    a[i] = k; // critical

    quick_sort(a, l, i-1);
    quick_sort(a, i+1, r);
}

void bubble_sort(int a[], int n)
{
    int i, j;
    int tmp;

    for (i=0; i<n; i++)
    {
        for (j=0; j<n-i-1; j++)
        {
            if (a[j] > a[j+1])
            {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

void bubble_sort1(int a[], int n)
{
    int tmp;
    int flag = 1;
    int i;

    while (flag)
    {
        n--;
        flag = 0;
        for (i=0; i<n; i++)
        {
            if (a[i] > a[i+1])
            {
                tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
                flag = 1;
            }
        }
    }
}

void shell_sort(int a[], int n)
{
    int gap, i, j, tmp;

    for (gap=n/2; gap>0; gap/=2)
    {
        for (i=gap; i<n; i++)
        {
            tmp = a[i];
            for (j=i-gap; j>0 && a[j]>tmp; j-=gap)
            {
                a[j+gap] = a[j];
            }
            a[j+gap] = tmp;
        }
    }
}

void insert_sort(int a[], int n)
{
    int i, j, tmp;

    for (i=1; i<n; i++)
    {
        tmp = a[i];
        for(j=i-1; j>=0 && a[j]>tmp; j--)
        {
            a[j+1] = a[j];
        }
        a[j+1] = tmp;
    }
}

void merge_array(int a[], int mid, int n, int tmp[])
{
    int i = 0, imax = mid;
    int j = mid, jmax = n;
    int k = 0;

    while (i < imax && j < jmax)
    {
        tmp[k++] = (a[i]<a[j]) ? a[i++] : a[j++];
    }

    while (i < imax)
    {
        tmp[k++] = a[i++];
    }

    while (j < jmax)
    {
        tmp[k++] = a[j++];
    }

    for (k=0; k<n; k++)
    {
        a[k] = tmp[k];
    }
}

void merge_sort(int a[], int n, int tmp[])
{
    if (n <= 1)
    {
        return;
    }

    merge_sort(a, n/2, tmp);
    merge_sort(a+n/2, n-n/2, tmp);
    merge_array(a, n/2, n, tmp);
}


#define N    10
int a[] = {17, 23, 43, 12, 24, 46, 42, 32, 23, 13};

main()
{
    int tmp[N];


    print_array(a, N);

    //quick_sort(a, 0, N-1);
    //bubble_sort(a, N);
    //bubble_sort1(a, N);
    //shell_sort(a, N);
    //insert_sort(a, N)；
    merge_sort(a, N, tmp);

    print_array(a, N);
}