package Ġcom . github . sol air er ove . al gs 4 . le pro sor ium . sorting Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġitems Ġ= Ġmutable ListOf ( 5 , Ġ 6 , Ġ 4 , Ġ 3 , Ġ 1 0 , Ġ 9 , Ġ 5 , Ġ 6 , Ġ 7 ) ĊĠĠĠ Ġprint (" items : Ġ$ items Ġ\ n ") ĊĠĠĠ Ġmerge Sort ( items ) ĊĠĠĠ Ġprint (" items : Ġ$ items Ġ\ n ") Ċ } Ċ Ċ // ĠO ( n log ( n )) Ġtime Ġ| ĠO ( n ) Ġspace Ċ private Ġfun Ġmerge Sort ( arr : ĠMutable List < Int >) Ġ{ ĊĠĠĠ Ġval Ġn Ġ= Ġarr . size ĊĊĠĠĠ Ġval Ġaux Ġ= ĠMutable List ( n ) Ġ{ Ġi Ġ-> Ġi Ġ} ĊĠĠĠ Ġmerge Sort ( arr , Ġaux , Ġ 0 , Ġn Ġ- Ġ 1 ) Ċ } Ċ Ċ private Ġfun Ġmerge Sort ( arr : ĠMutable List < Int >, Ġaux : ĠMutable List < Int >, Ġlow : ĠInt , Ġhigh : ĠInt ) Ġ{ ĊĠĠĠ Ġif Ġ( high Ġ<= Ġlow ) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġmid Ġ= Ġlow Ġ+ Ġ( high Ġ- Ġlow ) Ġ/ Ġ 2 ĊĊĠĠĠ Ġmerge Sort ( arr , Ġaux , Ġlow , Ġmid ) ĊĠĠĠ Ġmerge Sort ( arr , Ġaux , Ġmid Ġ+ Ġ 1 , Ġhigh ) ĊĠĠĠ Ġmerge ( arr , Ġaux , Ġlow , Ġmid , Ġhigh ) Ċ } Ċ Ċ private Ġfun Ġmerge ( arr : ĠMutable List < Int >, Ġaux : ĠMutable List < Int >, Ġlow : ĠInt , Ġmid : ĠInt , Ġhigh : ĠInt ) Ġ{ ĊĠĠĠ Ġvar Ġi Ġ= Ġlow ĊĠĠĠ Ġvar Ġj Ġ= Ġmid Ġ+ Ġ 1 ĊĊĠĠĠ Ġfor Ġ( k Ġin Ġlow .. high ) Ġ{ ĊĠĠĠĠĠĠĠ Ġaux [ k ] Ġ= Ġarr [ k ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfor Ġ( k Ġin Ġlow .. high ) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ> Ġmid Ġ-> Ġarr [ k ] Ġ= Ġaux [ j ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ> Ġhigh Ġ-> Ġarr [ k ] Ġ= Ġaux [ i ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġaux [ j ] Ġ< Ġaux [ i ] Ġ-> Ġarr [ k ] Ġ= Ġaux [ j ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġarr [ k ] Ġ= Ġaux [ i ++] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ