需要借助一个数组,时间复杂度为O(nlogn),空间复杂度为O(n)
#include <stdio.h> #include <iostream> #include <vector> #include <stack> #include <algorithm> #include <string> using namespace std; void Merge(vector<int>&arr, vector<int>&tmp, int l, int k, int r) { int i = l; int j = k + 1; int p = l; while (i <= k&&j <= r) { if (arr[i] < arr[j]) tmp[p++] = arr[i++]; else tmp[p++] = arr[j++]; } while (i <= k) tmp[p++] = arr[i++]; while (j <= r) tmp[p++] = arr[j++]; for (i = l; i <= r; ++i) arr[i] = tmp[i]; } void MSort(vector<int>&arr, vector<int>&tmp, int l, int r) { if (l >= r) return; int k = (l + r) / 2; MSort(arr, tmp, l, k); MSort(arr, tmp, k + 1, r); Merge(arr, tmp, l, k, r); } void MergeSort(vector<int>&arr) { vector<int> tmp(arr.size()); MSort(arr, tmp, 0, arr.size() - 1); } int main() { vector<int> arr = { 12,1 , 123, 1, 4, 2, 54, 3, 52, 3, 12, 4, 123,55 , 135 }; MergeSort(arr); return 0; }