[問題] Merge Sort v.s. Quick Sort

[MBS550L (uu8nc)]

大家好

小弟在測試merge sort 與 quick sor時發現

在一百萬筆long int的case下測試多次發現

merge sort的平均速度約為70ms

而quick sort的平均速度約為130ms

差了將近一倍 怎麼會這樣?

我是用隨機的亂數輸入陣列

而為了不要元素有那麼多重複的

我是用rand()*rand()

為甚麼quick sort會比merge sort慢了將近一倍@@

這邊用的演算法都是最基礎的 沒有經過改良

還請各位大大幫我解惑了 查了許多資料都沒查到QQ

這是我的code https://ideone.com/Glm92N
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 116.241.212.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1623822807.A.444.html
→ ckvir: 是每次嗎？應該和選的 pivot 位置有關
→ MBS550L: 樓上大大是每次沒錯，我的快排都是選v[0]當pivot
※ 編輯: MBS550L (116.241.212.216 臺灣), 06/16/2021 14:15:59
推 windada2: quick sort 在 pivot 選的最差的情況下是 O(n^2)
→ windada2: 而 merge sort 是很穩定的 O(n*logn)
→ sarafciel: 你有驗證過你寫的兩個sort的正確性了嗎?
推 paintlife08: 第131、136行，陣列v好像都事先被第126行排序了.
→ MBS550L: 各位不好意思= = 我m-sort的code有問題，不過無法自刪就
→ MBS550L: 給大家當笑話看吧哈哈 debug之後q-sort是最快的沒錯...
→ final01: 有沒有quick sort不是最快的八卦XD
→ Lipraxde: 基於比較的排序法的話...可以這麼說吧
推 Schottky: 特殊狀況下是有比 quick sort 還快的排序啊，
→ Schottky: 比如 distribution counting 是 O(N)