A4の紙が100枚程度あり，そのそれぞれの紙の左上に通し番号が書いてあるものとする．現在は紙に書かれた番号はランダムに並べ替えられてひと束になっているものとする．
（問題）この紙の束の並び順を変えて，通し番号の順に上から並んでいるようにしたい．ただし，できるだけ狭い面積でこの作業を効率よく行いたい．たとえば，新幹線の席に座りながらこの作業を行う（作業スペースはA4紙２枚程度）ならどうか．
問題のポイントは n log(n)のオーダーのソーティングを膝の上だけでできるか，ということである．なんとなくできるような気はするが，うまくいくかな？
（問題）この紙の束の並び順を変えて，通し番号の順に上から並んでいるようにしたい．ただし，できるだけ狭い面積でこの作業を効率よく行いたい．たとえば，新幹線の席に座りながらこの作業を行う（作業スペースはA4紙２枚程度）ならどうか．
問題のポイントは n log(n)のオーダーのソーティングを膝の上だけでできるか，ということである．なんとなくできるような気はするが，うまくいくかな？