题解 | #合并两个排序的链表#

int* MySort(int* arr, int arrLen, int* returnSize ) {
// write code here

//---------------还是得用希尔排序

int d;//增量
int i,j,temp;
//增量一开始为总长度的一半，每次结束后除以2作为下一次的增量。
//只要增量大于0，就继续排序
for(d=arrLen/2 ; d>0 ; d=d/2)
{
    //从未排序区域的第一个数值往后遍历
    for(i=d; i<arrLen ; i++)
    {
        temp = arr[i];//临时变量等于未排序区域中拿出来比较的数值
        j = i;//j是从未排序区域中拿出来比较的数值的下标

        if( temp < arr[j-d])
        {
            while(  j-d>=0 && temp< arr[j-d])
            {
                arr[j] = arr[j-d];
                j = j-d;
            }
            arr[j]=temp;
        }
    }
}
 *returnSize = arrLen;
return arr;

}