题目描述：
Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.
Have you met this question in a real interview? Yes ExampleGiven [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].
题目思路：今天喜欢merge sort，就用merge sort好了。需要注意的是，在merge两个sorted array时，需要开辟一个新的array用来存原来的A中start~end的值，否则直接在A上做in-place是会wrongly overwrite的。这个新的array必须是长度为end-start+1的，之前我偷懒直接开了一个A的copy，结果就不能pass lintcode的空间复杂度了。
Mycode（AC = 501ms）：
class Solution { public: /** * @param A an integer array * @return void */ void sortIntegers2(vector<int>& A) { // Write your code here mergeSort(A, 0, A.size() - 1); } void mergeSort(vector<int>& A, int start, int end) { if (start >= end) return; // sort the left half and right half in A mergeSort(A, start, (start + end) / 2); mergeSort(A, (start + end) / 2 + 1, end); // merge the two sorted arrays merge(A, start, (start + end) / 2, end); } void merge(vector<int>& A, int start, int mid, int end) { // use a tmp array to store A:start ~ end vector<int> tmp(end - start + 1, 0); int A_idx = start; for (int i = 0; i < tmp.size(); i++) { tmp[i] = A[A_idx++]; } int l = 0, r = mid + 1 - start, idx = start; // merge the sorted arrays while (l <= mid - start && r < tmp.size()) { if (tmp[l] <= tmp[r]) { A[idx++] = tmp[l++]; } else { A[idx++] = tmp[r++]; } } while (l <= mid - start) A[idx++] = tmp[l++]; while (r < tmp.size()) A[idx++] = tmp[r++]; } };