Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Example

```
Input Result
[3, 2, 1] [1, 2, 3]
[3, 2, 1, 4, 5] [1, 2, 3, 4, 5]
```

The following is an implementation of merge sort, which has time complexity of O(nlogn) and space complexity of O(n).