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.

page revision: 17, last edited: 30 Apr 2012 07:01