希尔排序与归并排序都是分组进行比较，但是希尔排序是组间比较，归并排序是组内排序

希尔排序

设置一个增量gap，从第0个数开始到这个增量之间，每隔增量个位置的所有数组成一个分组，一共gap个分组，在每个分组内进行插入排序，然后把各个分组的数按顺序放回去。然后再把增量缩小一半重新进行上面的操作，一直到gap为1；数组排序完成。

void SortManager::shellSort(int *arr,int len)
{
    int gap= len;
    while (true) {
        gap=gap/2;
        for (int i = 0; i<gap; i++) {
            for (int j = i + gap; j<len; j = j + gap) {
                //插入排序
                int temp = arr[j];
                int k = j-gap;
                while (k >= 0 && arr[k] > temp) {
                    arr[k + gap] = arr[k];
                    k = k-gap;//要对比的元素在原数组中下标相隔gap
                }
                arr[k + gap] = temp;
                //插入排序结束
            }
        }

        if (gap == 1)
            break;
    }
    printArr(arr, len);
}

归并排序

归并排序需要消耗多余的空间，是一种以空间换时间的算法。
把每个元素当成一个组，每两组间的元素比较，把小的放在前面，大的放在后面组成一个新的组，组数个是前面的一半，再把新的组两两比较，再合并，直到合并成一个大数组。下面代码采用递归的方式形式实现。由于每组内的元素都是经过一次排序，所以递归到上面的大数组时，比较次数会变少。

void merge(int *sourceArr,int *tempArr, int startIndex, int midIndex,int endIndex)
{
    int i = startIndex;
    int j = midIndex+1;
    int k = startIndex;
    while (i != midIndex + 1 && j != endIndex+1) {
        if (sourceArr[i]>=sourceArr[j]) {
            tempArr[k++] = sourceArr[j++];
        }else{
            tempArr[k++] = sourceArr[i++];
        }
    }
    //剩下的元素肯定比temp里的所有元素都大因为，数组较多的元素也是比较过大小组起气来的，d所以直接跟在后面就可以了
    while (i != midIndex + 1) {
        tempArr[k++] = sourceArr[i++];
    }
    
    while (j != endIndex + 1) {
        tempArr[k++] = sourceArr[j++];
    }
    
    for (i = startIndex; i<=endIndex; i++) {
        sourceArr[i] = tempArr[i];
    }
}

void SortManager::mergeSort(int *sourceArr,int *tempArr,int startIndex,int endIndex)
{
    int midIndex;
    if (startIndex<endIndex) {
        midIndex = startIndex + (endIndex - startIndex)/2;
        mergeSort(sourceArr, tempArr, startIndex, midIndex);
        mergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
        merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}