普通にクイックソートでいいのでは

ソート時間の比較
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/speed-compare.html