おもしろい並び替えの話がありました。
↓こちらのバラバラの15本のしめじを背の順に並べるにはどうすればよいでしょうか?
わかりやすいように、背の高さを数字で表してみます。
しめじたちを真ん中の1番と5番の辺りで、2つに分けます。
(【11】【6】【3】【14】【12】【4】【9】【1】)(【5】【15】【10】【7】【13】【8】【2】)
そして、このグループをまた2つに分けます。
(【11】【6】【3】【14】)(【12】【4】【9】【1】)(【5】【15】【10】【7】)(【13】【8】【2】)
さらに2つに分けていき、それぞれのグループが2つになるまで分けると、8つのグループができました。
(【11】【6】)(【3】【14】)(【12】【4】)(【9】【1】)(【5】【15】)(【10】【7】)(【13】【8】)(【2】)
それぞれのグループで、長い方を右側に置きます。
(【6】【11】)(【3】【14】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
次に、一番左のグループとその隣のグループの長い方を上に置き2つを比べます。
【11】【14】←ココ
(【6】空)(【3】空)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
長さの勝った方を残します。負けた方はいったん元に戻します。
【14】
(【6】【11】)(【3】空)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
となりにあった短いものと、今負けたものを比べます。
【14】
【11】【3】←ココ
(【6】空)(空 空)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
勝った方を残し、負けた方は元に戻します。
【11】【14】
(【6】【空】)(【3】【空】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
最後に残った2本を比べて同じようにすれば、
【11】【14】
【6】【3】←ココ
(【空】 【空】)(【空】 【空】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
キレイに並んだ4本組ができます。
(【3】【6】【11】【14】)
(【空】 【空】)(【空】 【空】)(【4】【12】)(【1】【9】)(【5】【15】)(【7】【10】)(【8】【13】)(【2】)
他のも同じようにすると、↓こうなります。
(【3】【6】【11】【14】)(【1】【4】【9】【12】)(【5】【7】【10】【15】)(【2】【8】【13】)
また隣のグループと背の高いもの同士を比べて並べるを
(【1】【3】【4】【6】【9】【11】【12】【14】)(【2】【5】【7】【8】【10】【13】【15】)
繰り返していくと、
(【1】【2】【3】【4】【5】【6】【7】【8】【9】【10】【11】【12】【13】【14】【15】)
全部キレイに並びました。