## Sunday, October 9, 2016

### merge sort and its time complexity

Here is the javascript implementation.
```
function mergeSort(arr) {
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (left <= right) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}
``` The time complexity is O(nlogn). It need divide all elements into two groups until one group has only 2 elements ( or 3 elemetns).
Sort in each group.
Merge two groups, compare the first element for each group, pop the small one into the result array; Then repeat the step again, when one group has no item, the values in the other group can be appended to the end of the result array.
For each stage, the compare time is n/2.
How many stage is there? divide all elements by 2, until the result is 2, so it is log2 n.
So the time complexity is O(n/2*log2 n) ==> O(nlogn)

The space complexity (memory usage) is O(n).