老師你好，我是用VSCode的學生，我想請問，為什麼我的三路快排並沒有比雙路來的快呢?
甚至比MergeSort還慢了點…
[以下附上程式碼]

#include <iostream>

#include "sortTestHelper.h"
using namespace std;

template <class T>
void insertionSort(T arr[], int l, int r) {
    for (int i = l; i <= r; i++) {
        T v = arr[i];
        int j;
        for (j = i; j > l; j--) {
            if (arr[j - 1] > v) {
                arr[j] = arr[j - 1];
            } else {
                break;
            }
        }
        arr[j] = v;
    }
}

//將[l,r]兩部分合併成一部分
template <class T>
void __merge(T arr[], int l, int mid, int r) {
    //創建臨時空間
    T aux[r - l + 1];  //大小是l~r
    //將arr[l]~arr[r]所有值拷貝到aux陣列中
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }

    //i指向左邊陣列的頭,j指向又邊陣列的頭
    int i = l, j = mid + 1;

    //開始決定排完序後的arr每個元素應該是誰
    for (int k = l; k <= r; k++) {
        //如果任一組陣列已經被取光
        if (i > mid) {  //左邊取光
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {  //右邊取光
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {  //右邊大於左邊
            arr[k] = aux[i - l];               //存放左邊
            i++;                               //移動到下一個位置
        } else {
            arr[k] = aux[j - l];  //存放右邊
            j++;                  //移動到下一個位置
        }
    }
}

//MergeSort Buttom up
template <class T>
void mergeSortBU(T arr[], int n) {
    //每次看1,2,4,8...個元素
    for (int size = 1; size <= n; size += size) {
        //i+=(size+size)--->每次看的元素
        for (int i = 0; i + size < n; i += size + size) {
            //min(i + size + size - 1, n - 1):可能少於size個元素
            __merge(arr, i, i + size - 1, min(i + size + size - 1, n - 1));
        }
    }
}

//做partition 返回p 使得[l...p-1]<arr[p];arr[p+1...r]>arr[p]
template <class T>
int __partition2(T arr[], int l, int r) {
    //隨機化排序--->避免近乎有序時，產生的樹 左右不平衡
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    int i = l + 1, j = r;  //arr[l+1...i]<=v;arr(j...r]>=v

    while (true) {
        //如果arr[i]一直小於v將i往後移動
        while (i <= r && arr[i] < v) {  //防止i越界
            i++;
        }
        //如果arr[j]一直大於v將j往前移動
        while (j >= l + 1 && arr[j] > v) {
            j--;
        }

        //兩個while迴圈結束後會有兩種三種狀況
        //兩個值等於v或者大於/小於v
        //或者全部都檢查完
        if (i > j) {  //i和j相遇並錯過--->檢查完成
            break;
        }
        //交換arr[i]與arr[j]
        swap(arr[i], arr[j]);
        //移動i j
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

//對[l,r]做快速排序
template <class T>
void __quickSort2(T arr[], int l, int r) {
    if (r - l <= 15) {  //陣列小的時候--->改用insertionSort
        insertionSort(arr, l, r);
        return;
    }

    int p = __partition2(arr, l, r);
    //快速排序 左右陣列
    __quickSort2(arr, l, p - 1);  //左半邊比arr[p]小的
    __quickSort2(arr, p + 1, r);  //右半邊比arr[p]大的
}

template <class T>
void quickSort2(T arr[], int n) {
    //隨機快速排序
    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

template <class T>
void __quickSort3(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    }

    //三路partition
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    int lt = l;      //arr[l+1...lt]<v
    int gt = r + 1;  //arr[gt...r]>v
    int i = l + 1;   //arr[lt+1...i)==v--->因為arr[i]最後會跟v做swap

    while (i < gt) {       //還未掃瞄到最後
        if (arr[i] < v) {  //前到後
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        } else if (arr[i] > v) {  //後到前
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else {  //arr[i]==v
            i++;
        }
    }

    swap(arr[l], arr[lt]);

    __quickSort3(arr, l, lt - 1);  //排序小於v的元素
    __quickSort3(arr, gt, r);      //排序大於v的元素
}

template <class T>
void quickSort3(T arr[], int n) {
    srand(time(NULL));
    __quickSort3(arr, 0, n - 1);
}

int main() {
    int n = 100000;
    int swapTimes = 100;
    int *arr = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
    int *arr1 = SortTestHelper::copyIntArray(arr, n);
    int *arr2 = SortTestHelper::copyIntArray(arr, n);
    int *arr3 = SortTestHelper::copyIntArray(arr, n);

    SortTestHelper::testSort("MergeBU", mergeSortBU, arr1, n);
    SortTestHelper::testSort("QuickSort2", quickSort2, arr2, n);
    SortTestHelper::testSort("QuickSort3", quickSort3, arr3, n);

    return 0;
}

[執行結果]