Merge Sort

Code

static int list[];
void mergesort(int left, int right)
{
    int mid;
    if (left < right) {                        // for the extreme case: left == right, the function directly return, do nothing to the list
        mid = (left + right)/2;                 // mid is floor[left+right]; the left part is [left, mid], and the right part is [mid+1, right]
        mergesort(left, mid);
        mergesort(mid + 1, right);
 
        merge(left, mid, right);               // after obtaining the sorted two parts, merge them. 
    }
}
 
void merge(int left, int mid, int right)
{
    int temp[right-left+1];
    int i, j, k;
    i = left; 
    j = mid + 1;
    k = 0;
 
    while (i <= mid && j <= right) {      // one of the two arrays must finish first
        if (list[i] <= list[j])
             temp[k++] = list[i++];
        else 
             temp[k++] = list[j++];    
    }
 
    if (i > mid)                                      // copy the remainder items to the temporary list
          while (j <= right)
                temp[k++] = list[j++];
    else 
          while (i <= mid) 
                temp[k++] = list[i++];
 
    for (i = left, k = 0; i <= right; i++, k++) // copy the temporary list to the original list, i: left ->right, not 0 -> right-left+1
          list[i] = temp[k];
}

Time Complexity

  • Best / Worst / Avg = O(nlogn)

Space Complixity

  • O(n) — The depth of the recursion tree is logn, and that introduces space complexity of O(logn). However, the merge step allocates array of size n, and that is space complexity of O(n). Therefore, the space complexity is O(n), which is dominated by the merge function.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License