package Ġsort Ċ Ċ /** Ċ Ġ* ĠThis Ġmethod Ġimplements Ġthe ĠGeneric ĠInsert ion ĠSort Ċ Ġ* Ċ Ġ* Ġ@ param Ġarray ĠThe Ġarray Ġto Ġbe Ġsorted Ċ Ġ* ĠSort s Ġthe Ġarray Ġin Ġincreasing Ġorder Ċ Ġ* Ċ Ġ* ĠW or st - case Ġperformance ĠĠĠ ĉ O ( n ^ 2 ) Ċ Ġ* ĠBest - case Ġperformance ĠĠĠĠ ĉ O ( n ) Ċ Ġ* ĠAverage Ġperformance ĠĠĠĠĠĠ ĉ O ( n ^ 2 ) Ċ Ġ* ĠW or st - case Ġspace Ġcomplexity ĉ O ( 1 ) Ċ Ġ**/ Ċ fun Ġ< T Ġ: ĠComparable < T >> Ġinsertion Sort ( array : ĠArray < T >) Ġ{ ĊĠĠĠ Ġval Ġsize Ġ= Ġarray . size Ġ- Ġ 1 ĊĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġkey Ġ= Ġarray [ i ] ĊĠĠĠĠĠĠĠ Ġvar Ġidx Ġ= Ġi ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġi Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array [ j ] Ġ> Ġkey ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ j Ġ+ Ġ 1 ] Ġ= Ġarray [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġidx Ġ= Ġj ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġarray [ idx ] Ġ= Ġkey ĊĠĠĠ Ġ} Ċ }