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
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License