>>883
O(n)にはならないように思うのですが。
整列が完了したら、参照されなくなったリストはGCされますが、整列中の間は参照されているわけですからGCされませんよね？
再帰呼び出しごとに新しいリストが作られ、それらは呼び出しから戻らないとGCされませんが、呼び出しから戻る前に別の再帰呼び出しが発生するわけだから、やはりメモリ消費量はO(n)ではないと思います。
また再帰呼び出しの深さは最大n-1になるので、やはりO(n^2)ではないでしょうか。実際には、呼び出しの深さは平均でlog(n)でしょうから、 O(n*log(n))が正解かもしれませんが。
詳しい人、お願いします。