/* shellsort，按递增顺序对v[0]...v[n-1]进行排序 */
void shellsort(int v[], int n) {
    int gap, i, j, temp;
    /* 控制两个被比较元素之间的距离 */
    for (gap = n/2; gap > 0; gap /= 2)
        /* 用于在元素间移动位置，使每一组间隔gap的元素排序 */
        for (i = gap; i < n; i++)
            /* 从最左边开始，每隔gap取一个元素，排序
             * 注意当取到该组的第k个元素时，组内之前的元素已经排好序了
             * 所以之需要找到组内从右向左第一个小于它的元素，并把第k个元素
             * 与这个元素后面的那个元素互换，就能保证这k个元素是排好序的
             */
            for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }
}

void swap(int v[], int i, int j) {
    int tmp;
    tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
}

/* 快速排序，对v[left] ... v[right]进行排序 */
void qsort(int v[], int left, int right) {
    int i, last;
    if (left >= right)
        return;

    /* 取中间一个元素为划分子集的元素, 并且把它和第一个元素交换 */
    swap(v, left, (left + right)/2);
    /* last表示的位置是其左边（包括它自己）的所有元素都小于特定元素 */
    /* 首先把last定位到开头，然后逐个比较元素是否小于特定元素 */
    /* 如果小于的话，就把它和last的下一位交换，同时last增加1 */
    /* 这样仍然满足last以及last之前的所以元素都小于特定元素 */
    last = left;
    /* 由于之前已经把特定元素放到开头了，所以从第二个元素开始和v[left]比较 */
    for (i = left+1; i <= right; i++)
        /* 如果小于的话，就把它和last的下一位交换，同时last增加1 */
        if (v[i] < v[left])
            swap(v, ++last, i);
    /* 注意，一开始的时候我们是把特定元素放到第一项的， 而last表示的是小于 */
    /* 特定元素的最后一项，现在交换它们的位置，也就是把特定元素放到中间 */
    /* 左边的都小于它，右边的都大于它 */
    swap(v, left, last);

    /* 对剩下的两部分进行同样的操作 */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

/*
 * 归并排序
 */

/*
 * v[row]到r[m]和r[m+1]到r[high]是存储在同一个数组中且相邻的两个有序的子文件
 * merge函数将这两个子文件合并成一个有序的文件，并存放在v1[low]到v1[high]中
 */
void merge(int v[], int v1[], int low, int m, int high) {
    int i = low;
    int j = m + 1;
    int k = low;
    /* 不断从两个有序文件中的第一个记录中选出最小的记录 */
    while ((i <= m) && (j <= high)) {
        if (v[i] <= v[j])
            v1[k++] = v[i++];
        else
            v1[k++] = v[j++];
    }
    /* 分别复制两个文件的剩余记录，事实上只会有一个文件有记录 */
    while (i <= m)
        v1[k++] = v[i++];
    while (j <= high)
        v1[k++] = v[j++];
}

/*
 * 一趟归并算法，对长度为n的v做一趟归并，结果放在v1中, seg表示子文件的长度
 * 子文件应该是：v[0]~v[seg-1], v[seg]~v[2*seg-1], ...
 * 要注意，最后一个的长度有可能小于seg
 */
void merge_pass(int v[], int v1[], int size, int seg) {
    int i = 0;
    int j = 0;
    /* 两个两个地对文件进行归并 */
    while (i + 2 * seg -1 < size) {
        merge(v, v1, i, i+seg-1, i+2*seg-1);
        i += 2 * seg;
    }

    if (i+seg-1 < size-1)    /* 剩下两个文件，其中一个长度可能小于seg */
        merge(v, v1, i, i+seg-1, size-1);
    else                  /* 只剩下最后一个文件，直接复制即可 */
        for (j=i; j<size; j++)
            v1[j] = v[j];
}

/*
 * 二路归并算法
 * 通过改变seg的大小一边一遍地对数据进行merge_pass
 */
void merge_sort(int v[], int size) {
    int *temp = malloc(size * sizeof(int));
    int seg = 1;
    while (seg < size) {
        /* 把v进行一趟归并，存放到temp中 */
        merge_pass(v, temp, size, seg);
        seg += seg;
        /* 增加seg的值后对temp进行一次归并，存放到v中 */
        merge_pass(temp, v, size, seg);
        seg += seg;
    }
    free(temp);
}