我的感覺

來源: 於 2009-08-17 16:11:02 [博客] [舊帖] [給我悄悄話] 本文已被閱讀：次

排列8個數，如果用merge sort，最少要17次才能保證排好。而2^16>8!
所以懷疑22次不能保證排好。

直觀解釋就是總有運氣好的時候，可以讓最後一次比較不重要，而且這種情況還不少（最少占一半），這樣這棵樹就無法平衡。不知道對不對？