大家好
小弟在測試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

是每次嗎？應該和選的 pivot 位置有關

樓上大大是每次沒錯，我的快排都是選v[0]當pivot

quick sort 在 pivot 選的最差的情況下是 O(n^2)而 merge sort 是很穩定的 O(n*logn)

你有驗證過你寫的兩個sort的正確性了嗎?

第131、136行，陣列v好像都事先被第126行排序了.

各位不好意思= = 我m-sort的code有問題，不過無法自刪就給大家當笑話看吧哈哈 debug之後q-sort是最快的沒錯...

有沒有quick sort不是最快的八卦XD

基於比較的排序法的話...可以這麼說吧

特殊狀況下是有比 quick sort 還快的排序啊，比如 distribution counting 是 O(N)