1 #include <iostream>

 2 #include<vector>

 3 using namespace std;

 4

 5 void merge_func(vector<int> &v, int l, int m, int r)

 6 {

 7     vector<int> t;

 8     int p=l, q=m+1;

 9     while(p<=m && q<=r)

10     {

11         if(v[p]>v[q])

12         {

13             t.push_back(v[q]);

14             q++;

15         }

16         else

17         {

18             t.push_back(v[p]);

19             p++;

20         }

21     }

22     while(p<=m)

23         t.push_back(v[p++]);

24     while(q<=r)

25         t.push_back(v[q++]);

26

27     for(int i=l;i<=r;i++)

28         v[i] = t[i-l];

29

30 }

31

32 void merge_sort(vector<int> &v, int l, int r)

33 {

34     if(l<r)

35     {

36         int m = l+(r-l)/2;   //先找到中点位置

37         merge_sort(v,l,m);   //左侧归并排序

38         merge_sort(v,m+1,r);  //右侧归并排序

39         merge_func(v,l,m,r);  //合并左侧和右侧

40     }

41 }

42

43 int main()

44 {

45     vector<int> v={6,4,2,3,1,5};

46     //vector<int> v={3,6,1,2,4,7,5};

47     merge_sort(v,0,v.size()-1);

48     for(auto i:v)

49         cout<<i<<endl;

50     return 0;

51 }