归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

Code

void merge(int sourceArray[],int newArray[],int startIndex,int midIndex,int endIndex) {
    int i = startIndex;
    int n = startIndex;
    int j = midIndex + 1;
    while (i != midIndex + 1 && j!= endIndex + 1) {
        if (sourceArray[i] > sourceArray[j]) {
            newArray[n] = sourceArray[j];
            j++;
        } else {
            newArray[n] = sourceArray[i];
            i++;
        }
        n++;
    }
    while (i != midIndex + 1) {
        newArray[n] = sourceArray[i];
        i++;
        n++;
    }
    while (j != endIndex + 1) {
        newArray[n] = sourceArray[j];
        j++;
        n++;
    }
    for (int k = startIndex; k <= endIndex; k++) {
        sourceArray[k] = newArray[k];
    }
}

void mergeSort (int sourceArray[],int newArray[],int startIndex,int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int midIndex = startIndex + (endIndex - startIndex)/2;
    mergeSort(sourceArray,newArray,startIndex,midIndex);
    mergeSort(sourceArray,newArray,midIndex + 1,endIndex);
    merge(sourceArray, newArray,startIndex,midIndex,endIndex);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int array[17] = {3,5,3,20,8,6,23,5,7,9,2,3,0,1,5,7,2};
        int newArray[17];
        mergeSort(array,newArray,0,16);
        for (int i = 0; i < 17; i++)
            printf("%d ", array[i]);
    }
    return 0;
}

Console

0 1 2 2 3 3 3 5 5 5 6 7 7 8 9 20 23 Program ended with exit code: 0

备注

算法代码化的过程中，一定要注意边界条件，边界条件就是最小子问题的几种组合

时间复杂度分析

• mergeSort

mergeSort(sourceArray,newArray,startIndex,midIndex);
mergeSort(sourceArray,newArray,midIndex + 1,endIndex);

这两句代码时间复杂度只有2，实际的任务递归到子任务去执行

• merge
  时间复杂度是2n，添加进newArray的时间复杂度为n，用newArray替换sourceArray时间复杂度为n
• 总时间复杂度
  递归树的层高为，时间复杂度为(2+2n)，所以时间复杂度为O(n)