Note/Algorithm/Basic/code/MergeSort.cpp at main · QiuBiuBiu/Note · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "Common.h"


template <typename T>
void _sort(std::vector<T>& nums, std::vector<T>& copy, int st, int end)
{
    if (st >= end) return;

    int mid = (end - st) / 2 + st;
    _sort(nums, copy, st, mid);
    _sort(nums, copy, mid + 1, end);

    int i = mid, j = end;
    int index = end;
    while (i >= st && j > mid)
    {
        if (nums[i] >= nums[j])
        {
            copy[index--] = nums[i--];
        }
        else
        {
            copy[index--] = nums[j--];
        }
    }
    while (i >= st) copy[index--] = nums[i--];
    while (j > mid) copy[index--] = nums[j--];

    for (int k = st; k <= end; k++)
    {
        nums[k] = copy[k];
    }
};

template <typename T>
void mergeSort(std::vector<T>& nums)
{
    int n = nums.size();
    if (n == 0) return;

    std::vector<T> copy;
    for (const auto& a : nums)
    {
        copy.emplace_back(a);
    }

    _sort(nums, copy, 0, n - 1);
};

int main()
{
    std::vector<int> a {9, 3, 4, 5, 6, 1, 2, 4};
    mergeSort(a);
    traversal(a);
    return 0;
}