Merge sort 穩定排序

#include <stdio.h>
#include <stdlib.h>
 
#define SORT_NUM 20
 
void print_array(int *list, int len);
void merge_array(int *list1, int list1_size, int *list2, int list2_size);
 
void merge_sort(int *list, int list_size)
{
    if (list_size > 1)
    {
        int *list1 = list;
        int list1_size = list_size / 2;
        int *list2 = list + list_size / 2;
        int list2_size = list_size - list1_size;
 
        merge_sort(list1, list1_size);
        merge_sort(list2, list2_size);
 
        merge_array(list1, list1_size, list2, list2_size);
    }
}
 
void merge_array(int *list1, int list1_size, int *list2, int list2_size)
{
    int i, j, k;
    i = j = k = 0;
 int ii = 0;
 
    int list[list1_size + list2_size];
 
    while (i < list1_size && j < list2_size)
    {
        list[k++] = list1[i] < list2[j] ? list1[i++] : list2[j++];
    }
 
    while (i < list1_size)
    {
        list[k++] = list1[i++];
    }
 
    while (j < list2_size)
    {
        list[k++] = list2[j++];
    }
 
    for (ii = 0; ii < (list1_size + list2_size); ++ii)
    {
        list1[ii] = list[ii];
    }
 
}
 
void print_array(int *list, int len)
{
    int i;
    for (i = 0; i < len; ++i)
    {
        printf("%3d", list[i]);
        if (i < len - 1)
            printf(" ");
    }
    printf("\n");
}
 
int main(void)
{
    int len = SORT_NUM;
    int list[len];
 int i = 0;
 srand(time(0)+getpid());
 
    for (i = 0; i < len; ++i)
    {
        list[i] = rand() % (SORT_NUM * SORT_NUM);
    }
  
    print_array(list, len);
    merge_sort(list, len);
    print_array(list, len);
 
    return 0;
}

參考wiki,做個備份
http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

code位置
https://drive.google.com/file/d/0B8hm-I2M8BD7N1drQTNhYWJHaEE/edit?usp=sharing