scalaスケールプログラミング P293

挿入ソートのプログラムが出ていた。挿入ソートのアルゴリズムも、昔見たような記憶もあるが、もう忘れている。少し整理して考えてみた。

def isort(xs: List[Int]):List[Int] =
 if(xs.isEmpty) Nil
 else insert(xs.head,isort(xs.tail))
def insert(x:Int,xs;List[Int]):List[Int] =
 if(xs.isEmpty || x <= xs.head)x::xs
else xs.head::insert(x,xs.tail)

isort(List())=Nil
isort(List(1))=insert(1,isort(List()))=insert(1,Nil)=List(1,Nil)

isort(List(2,1))=insert(2,isort(List(1)))=insert(2,List(1,Nil))=1::insert(2,Nil)=1::List(2,Nil)
=List(1,2,Nil)

isort(List(3,2,1))=insert(3,isort(List(2,1))=insert(3,List(1,2,Nil))=1::insert(3,List(2,Nil))
　　　　　　　　①　　　　　　　　　　② ③
=1::2::insert(3,Nil)=1::2::List(3,Nil)=List(1,2,3,Nil)

①isortはinsertで表せる。②insertの中のisortは最終的にソートされたListになっているが、
これに、③insertが再帰で適用されて、ソートされたListの適切な位置に挿入されれば、終了となる。　ということのようだ。