package Ġchapter 2 . section 2 Ċ Ċ import Ġchapter 2 . Array InitialState Ċ import Ġchapter 2 . enum ValueOf Ċ import Ġchapter 2 . getDouble Array Ċ import Ġchapter 2 . less Ċ import Ġextensions . delay Exit Ċ import Ġextensions . input Prompt Ċ import Ġextensions . readInt Ċ import Ġextensions . read Long Ċ Ċ /** Ċ Ġ* Ġ å½Ĵ å¹¶ æİĴåºı ï¼Ī èĩª é¡¶ åĲĳ ä¸ĭ ï¼ī Ċ Ġ*/ Ċ fun Ġ< T Ġ: ĠComparable < T >> Ġtop Down Merge Sort ( original Array : ĠArray < T >) Ġ{ ĊĠĠĠ Ġif Ġ( original Array . size Ġ<= Ġ 1 ) Ġreturn ĊĠĠĠ Ġval Ġextra Array Ġ= Ġoriginal Array . copyOf () ĊĠĠĠ Ġtop Down Merge Sort ( original Array , Ġextra Array , Ġ 0 , Ġoriginal Array . size Ġ- Ġ 1 ) Ċ } Ċ Ċ fun Ġ< T Ġ: ĠComparable < T >> Ġtop Down Merge Sort ( original Array : ĠArray < T >, Ġextra Array : ĠArray < T >, Ġstart : ĠInt , Ġend : ĠInt ) Ġ{ ĊĠĠĠ Ġif Ġ( start Ġ>= Ġend ) Ġreturn ĊĠĠĠ Ġval Ġmid Ġ= Ġ( start Ġ+ Ġend ) Ġ/ Ġ 2 ĊĠĠĠ Ġtop Down Merge Sort ( original Array , Ġextra Array , Ġstart , Ġmid ) ĊĠĠĠ Ġtop Down Merge Sort ( original Array , Ġextra Array , Ġmid Ġ+ Ġ 1 , Ġend ) ĊĠĠĠ Ġmerge ( original Array , Ġextra Array , Ġstart , Ġmid , Ġend ) Ċ } Ċ Ċ fun Ġ< T Ġ: ĠComparable < T >> Ġmerge ( original Array : ĠArray < T >, Ġextra Array : ĠArray < T >, Ġstart : ĠInt , Ġmid : ĠInt , Ġend : ĠInt ) Ġ{ ĊĠĠĠ Ġmerge Sort Callback List . forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġit . merge Start ( start , Ġend ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġfor Ġ( i Ġin Ġstart .. end ) Ġ{ ĊĠĠĠĠĠĠĠ Ġextra Array [ i ] Ġ= Ġoriginal Array [ i ] ĊĠĠĠ Ġ} ĊĠĠĠ Ġvar Ġi Ġ= Ġstart ĊĠĠĠ Ġvar Ġj Ġ= Ġmid Ġ+ Ġ 1 ĊĠĠĠ Ġvar Ġk Ġ= Ġstart ĊĠĠĠ Ġwhile Ġ( k Ġ<= Ġend ) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ> Ġmid Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmerge Sort Callback List . forEach Ġ{ Ġit . copy To Original ( j , Ġk ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoriginal Array [ k ++] Ġ= Ġextra Array [ j ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ> Ġend Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmerge Sort Callback List . forEach Ġ{ Ġit . copy To Original ( i , Ġk ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoriginal Array [ k ++] Ġ= Ġextra Array [ i ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// è¿ĻéĩĮ å¿ħé¡» åħĪ å¤ĦçĲĨ a [ j ]< a [ i ] çļĦ æĥħåĨµ ï¼Į ä¿Ŀè¯ģ a [ i ]== a [ j ] æĹ¶ åħĪ å°Ĩ å·¦ ä¾§ çļĦ a [ i ] èµĭåĢ¼ åĪ° a [ k ] ä¸Ń ï¼Į ä¿Ŀè¯ģ ç®Ĺæ³ķ çļĦ ç¨ ³ å®ļ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġextra Array . less ( j , Ġi ) Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmerge Sort Callback List . forEach Ġ{ Ġit . copy To Original ( j , Ġk ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoriginal Array [ k ++] Ġ= Ġextra Array [ j ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmerge Sort Callback List . forEach Ġ{ Ġit . copy To Original ( i , Ġk ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoriginal Array [ k ++] Ġ= Ġextra Array [ i ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġinput Prompt () ĊĠĠĠ Ġval Ġsize Ġ= Ġread Int (" size : Ġ") ĊĠĠĠ Ġval Ġdelay Ġ= Ġread Long (" delay Ġtime Ġmillis : Ġ") ĊĠĠĠ Ġval Ġordinal Ġ= Ġread Int (" array Ġinitial Ġstate ( 0 ~ 5 ): Ġ") ĊĠĠĠ Ġval Ġstate Ġ= Ġenum ValueOf < Array InitialState >( ordinal ) ĊĠĠĠ Ġval Ġarray Ġ= Ġget Double Array ( size , Ġstate ) ĊĠĠĠ Ġshow Merge Sort Process ( array , Ġ:: top Down Merge Sort , Ġdelay ) ĊĠĠĠ Ġdelay Exit () ĊĊĠĠĠ Ġ// è¿Ĳè¡Į æĹ¶éĹ´ æĽ² çº¿ åĽ¾ Ċ // ĠĠĠ Ġrunning Time Graph ( 5 0 0 _ 0 0 0 0 , Ġ:: top Down Merge Sort ) Ċ // ĠĠĠ Ġdelay Exit () ĊĊĠĠĠ Ġ// åıĮ åĢ į å¢ŀ éķ¿ æµĭè¯ķ Ċ // ĠĠĠ Ġdouble Grow th Test ( 1 0 0 0 _ 0 0 0 0 , Ġ:: top Down Merge Sort ) Ġ{ ĠN Ġ-> ĠN Ġ* Ġlog 2 ( N . toDouble ()) Ġ} ĊĊĠĠĠ Ġ// åĴĮ å¸Į å°Ķ æİĴåºı æĢ§èĥ½ å¯¹ æ¯Ķ Ċ // ĠĠĠ Ġval Ġsort Methods : ĠArray < Pair < String , Ġ( Array < Double >) Ġ-> ĠUnit >> Ġ= ĠarrayOf ( Ċ // ĠĠĠĠĠĠĠĠĠĠĠ Ġ" Shell ĠSort " Ġto Ġ:: shell Sort , Ċ // ĠĠĠĠĠĠĠĠĠĠĠ Ġ" Top ĠDown ĠMerge ĠSort " Ġto Ġ:: top Down Merge Sort Ċ // ĠĠĠ Ġ) Ċ // ĠĠĠ Ġsort Methods Compare ( sort Methods , Ġ 1 0 , Ġ 1 0 0 _ 0 0 0 0 , ĠArray InitialState . RANDOM ) Ċ }