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 ") ĊĠĠĠ Ġcount Sort ( items ) ĊĠĠĠ Ġprint (" items : Ġ$ items Ġ\ n ") Ċ } Ċ Ċ // ĠO ( n Ġ+ Ġm ) Ġtime Ġ| ĠO ( n ) Ġspace Ċ private Ġfun Ġcount Sort ( arr : ĠMutable List < Int >) Ġ{ ĊĠĠĠ Ġval Ġn Ġ= Ġarr . size ĊĊĠĠĠ Ġ// Ġfind Ġmax ĊĠĠĠ Ġvar Ġmax Ġ= Ġarr [ 0 ] ĊĠĠĠ Ġarr . forEach Ġ{ Ġif Ġ( it Ġ> Ġmax ) Ġmax Ġ= Ġit Ġ} ĊĊĠĠĠ Ġ// Ġinit Ġcount Ġwith Ġzeros ĊĠĠĠ Ġval Ġcount Ġ= ĠMutable List ( max Ġ+ Ġ 1 ) Ġ{ Ġ 0 Ġ} ĊĊĠĠĠ Ġ// Ġcount ĊĠĠĠ Ġarr . forEach Ġ{ Ġcount [ it ] ++ Ġ} ĊĊĠĠĠ Ġ// Ġcum ulate Ġsum ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. max ) Ġ{ ĊĠĠĠĠĠĠĠ Ġcount [ i ] Ġ+= Ġcount [ i Ġ- Ġ 1 ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġoutput Ġ= ĠMutable List ( n Ġ+ Ġ 1 ) Ġ{ Ġ 0 Ġ} ĊĠĠĠ Ġfor Ġ( i Ġin Ġn Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġoutput [ count [ arr [ i ]] Ġ- Ġ 1 ] Ġ= Ġarr [ i ] ĊĠĠĠĠĠĠĠ Ġcount [ arr [ i ]] -- ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġarr . forEach Indexed Ġ{ Ġi , Ġ_ Ġ-> Ġarr [ i ] Ġ= Ġoutput [ i ] Ġ} Ċ } Ċ