编译期归并排序

Chivas-Regal

# 运行期归并排序

回忆一下正常的归并排序是怎么写的
参数：虽然大多为 int l, int r ，实际目的是锁定出来一个数组，因此参数可以理解为数组
出口：数组为空或者只有一个元素时不用排，直接出
入口：对半分出两个数组，分别进入排序
操作：两数组的顺序合并

std::vector<int> a;
void Sort (int l, int r) {
    if (l >= r) return;

    int mid = (l + r) >> 1;
    Sort(l, mid); Sort(mid + 1, r);
    std::vector<int> b;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) b.push_back(a[i ++]);
        else b.push_back(a[j ++]);
    }
    while (i <= mid) b.push_back(a[i ++]);
    while (j <= r) b.push_back(a[j ++]);
    for (i = l; i <= r; i ++) a[i] = b[i - l];
}
int main () {
    a = {5, 4, 1, 6, 3, 2};
    Sort(0, a.size() - 1);
    for (int i : a) 
        std::cout << i << " "; 
}
/*
Output:
1 2 3 4 5 6
*/

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

# 编译期归并排序

排序的对象用我们这里声明好的编译期链表

# 操作：两升序数组升序合并

这个是归并的核心，但我们在前面链表删除中应该已经有回溯递归的思想了
在这里我们依然用回溯递归来完成操作
升序合并时先提出两者最小值，这样我们大致要判断一下提的是谁的，才能看子阶段是谁变成自己的 next
相信子阶段给出的链表是正确的，我们直接合并这个最小值和子阶段返回的链表

template<class ListObj1, class ListObj2> struct MergeBySort {};
template<int ...L, int ...R>
struct MergeBySort<List<L...>, List<R...>> {
    const static int __MIN_VALUE = Min<List<L...>::value, List<R...>::value>::value;
    // 子阶段
    using next = IF<
        List<L...>::value <= List<R...>::value,
        MergeBySort<typename List<L...>::next, List<R...>>, // 左被用了一个
        MergeBySort<List<L...>, typename List<R...>::next>  // 右被用了一个 
    >::ret;
    // 合并最小值和子阶段链表
    using ret = typename PushFront<__MIN_VALUE, typename next::ret>::ret;
};

1
2
3
4
5
6
7
8
9
10
11
12
13

# 整体：拆分排序后升序合并

和归并一样，我们将一个链表拆成两个链表，并将他们分别进入归并排序
信任排序的结果，用我们写好的升序合并两升序链表进行合并，即可得到排序后的链表，将它设置为返回值供上层使用
偏特化出口，即只有一个元素的链表没有必要排序，返回值为自己即可

template<class ListObj> struct Sort {};
template<int ...data>
struct Sort<List<data...>> {
    using ret = MergeBySort< // 合并两排序链表
        typename Sort<typename Split<List<data...>::size / 2, List<>, List<data...>>::_L>::ret, // 对左半链表排序
        typename Sort<typename Split<List<data...>::size / 2, List<>, List<data...>>::_R>::ret  // 对右半链表排序
    >::ret;
};
template<int data>
struct Sort<List<data>> {
    using ret = List<data>;
};

1
2
3
4
5
6
7
8
9
10
11
12

# 源代码

// 对两个升序链表升序合并
template<class ListObj1, class ListObj2> struct MergeBySort {};
template<int ...L, int ...R>
struct MergeBySort<List<L...>, List<R...>> {
    const static int __MIN_VALUE = Min<List<L...>::value, List<R...>::value>::value;
    using next = IF<
        List<L...>::value <= List<R...>::value,
        MergeBySort<typename List<L...>::next, List<R...>>,
        MergeBySort<List<L...>, typename List<R...>::next>
    >::ret;
    using ret = typename PushFront<__MIN_VALUE, typename next::ret>::ret;
};
template<int ...data>
struct MergeBySort<Null, List<data...>> {
    using ret = List<data...>;
};
template<int ...data>
struct MergeBySort<List<data...>, Null> {
    using ret = List<data...>;
};
// 归并排序
template<class ListObj> struct Sort {};
template<int ...data>
struct Sort<List<data...>> {
    using ret = MergeBySort<
        typename Sort<typename Split<List<data...>::size / 2, List<>, List<data...>>::_L>::ret,
        typename Sort<typename Split<List<data...>::size / 2, List<>, List<data...>>::_R>::ret
    >::ret;
};
template<int data>
struct Sort<List<data>> {
    using ret = List<data>;
};

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

编译期链表模板SFINAE