Sort - merge sort

Merge sort

Algorithm design

• Decompose a large problem into several sub problems for solution , The subproblem can be further decomposed , Until the scale of the problem can be solved directly .
• Divide the sequence into two subsequences , To make subsequences ordered , Then two ordered subsequences are merged into an ordered sequence

C Language implementation

void mergeSort(int* arr,int start,int end) {
    
    int len = end - start;
    if (len <= 1) {
    
        return;
    }
    int mid = (start+end)/2;
    mergeSort(arr,start,mid);
    mergeSort(arr,mid,end);
    int* temp = (int*)malloc(len * sizeof(int));
    int l=start,r=mid,index=0;
    while (l< mid && r < end) {
    
        if (arr[l] <= arr[r]) {
    
            temp[index] = arr[l];
            l++;index++;
        } else {
    
            temp[index] = arr[r];
            r++;index++;
        }
    }
    while (l < mid) {
    
        temp[index] = arr[l];
        l++;index++;
    }
    while (r < end) {
    
        temp[index] = arr[r];
        r++;index++;
    }
    for (l = start,index = 0; l < end; l++,index++) {
    
        arr[l] = temp[index];
    }
    free(temp);
}

Algorithm analysis

• The stability of the
• The space complexity is O(n)
• When two subsequences are output alternately one by one , The largest number of comparisons ; When one of the subsequences is output directly , Minimum number of comparisons . But the total time complexity is still O(nlogn)
• The average time complexity is zero O(nlogn)