プロファイル取って調べてみた。数字はtotal allocにqsortの%allocをかけたもの。左の数字は要素数。

>>881とランダム要素のリスト
800 : 380003.544
1600: 873076.32
2400: 1296538.048
3200: 1816425.728
4000: 2399276.16

>>885とランダム要素のリスト
800 : 400965.324
1600: 1040519.448
2400: 1389810.24
3200: 1846377.12
4000: 2776879.088

>>881と整列リスト（[1..n]）
800 : 8985561.144
1600: 35887143.13
2400: 80695069.14
3200: 143405095.9
4000: 224106868.3

>>885と整列リスト（[1..n]）
800 : 8995036.344
1600: 35906208.73
2400: 80723725.14
3200: 143443342.3
4000: 224154724.3

最悪ケースだとO(n^2)になるっぽい