Merge Sort

Monkey Forums/Monkey Code/Merge Sort

impixi (Posted 2011) [#1]

Sort an integer array using a recursive version of the 'merge sort' algorithm. Strict #rem MERGE SORT (December 2011) PORTED FROM C++ code located at: <a href="http://www.cprogramming.com/tutorial/computersciencetheory/merge.html" target="_blank">http://www.cprogramming.com/tutorial/computersciencetheory/merge.html</a> NOTE: Some browsers / platforms may have issues with deep levels of recursion. #end Function MergeSort:Void(input:Int[]) Local cache:Int[] = New Int[input.Length] RecursiveMergeSort input, 0, input.Length, cache End Function RecursiveMergeSort:Void(input:Int[], left:Int, right:Int, cache:Int[]) If (right = (left + 1)) Then Return Local length:Int = (right - left) Local mpDist:Int = Floor(length / 2) Local l:Int = left, r:Int = (left + mpDist) RecursiveMergeSort input, left, (left + mpDist), cache RecursiveMergeSort input, (left + mpDist), right, cache For Local i:Int = 0 Until length If ((l < (left + mpDist)) And ((r = right) Or (Max(input[l], input[r]) = input[l]))) cache[i] = input[l] l += 1 Else cache[i] = input[r] r += 1 Endif Next For Local i:Int = left Until right input[i] = cache[i - left] Next End '------- EXAMPLE -------------------------------- Function Main:Int() Local arr:Int[] = [10, -4, 19, 100, -22, 17, 92, 10, 4, 66, 2, 0, -2, -10, 4, 5] Local str:String = "-----------------------~nUnsorted:~n" For Local i:Int = 0 Until arr.Length str += arr[i] + ", " Next '************* MergeSort arr '************* str += "~n-----------------------~nSorted:~n" For Local i:Int = 0 Until arr.Length str += arr[i] + ", " Next str += "~n-----------------------~n" Print str Return 0 End

impixi (Posted 2011) [#2]

A class-embedded example: Strict #rem MERGE SORT (RECURSIVE): CLASS-EMBEDDED EXAMPLE (December 2011) #end Function Main:Int() Local players:Player[] = New Player[5] For Local i:Int = 0 Until players.Length players[i] = New Player("Player " + (i+1), Floor(Rnd(0.0, 1000.0))) Next Local str:String = "-----------------------~nUnsorted:~n" For Local i:Int = 0 Until players.Length str += players[i].name + ": " + players[i].score + "~n" Next '************* Player.SortArray players, Player.GET_SCORE_HIGH '************* str += "-----------------------~nSorted (descending, on score):~n" For Local i:Int = 0 Until players.Length str += players[i].name + ": " + players[i].score + "~n" Next '************* Player.SortArray players, Player.GET_NAME_HIGH '************* str += "-----------------------~nSorted (descending, on name):~n" For Local i:Int = 0 Until players.Length str += players[i].name + ": " + players[i].score + "~n" Next str += "-----------------------~n" Print str Return 0 End '**************************** Class Player Field name:String Field score:Int Method New(name:String, score:Int) Self.name = name Self.score = score End 'VVV SORTING-RELATED VVV Const GET_NAME_HIGH:Int = 0 Const GET_SCORE_HIGH:Int = 1 Const GET_NAME_LOW:Int = 2 Const GET_SCORE_LOW:Int = 3 Function Compare:Player(p1:Player, p2:Player, get:Int) Select get Case GET_NAME_HIGH If (p1.name > p2.name) Then Return p1 Else Return p2 Case GET_SCORE_HIGH If (p1.score > p2.score) Then Return p1 Else Return p2 Case GET_NAME_LOW If (p1.name < p2.name) Then Return p1 Else Return p2 Case GET_SCORE_LOW If (p1.score < p2.score) Then Return p1 Else Return p2 End Return Null End Global cache:Player[] Function SortArray:Void(input:Player[], sOn:Int) #rem Merge sort based on C++ code located at: <a href="http://www.cprogramming.com/tutorial/computersciencetheory/merge.html" target="_blank">http://www.cprogramming.com/tutorial/computersciencetheory/merge.html</a> #end If Not cache cache = New Player[input.Length] Else If (cache.Length <> input.Length) Then cache = cache.Resize(input.Length) Endif RecursiveMergeSort input, 0, input.Length, sOn End Function RecursiveMergeSort:Void(input:Player[], left:Int, right:Int, sOn:Int) 'NOTE: Some browsers / platforms may have issues with deep levels of recursion. If (right = (left + 1)) Then Return Local length:Int = (right - left) Local mpDist:Int = Floor(length / 2) Local l:Int = left, r:Int = (left + mpDist) RecursiveMergeSort input, left, (left + mpDist), sOn RecursiveMergeSort input, (left + mpDist), right, sOn For Local i:Int = 0 Until length If ((l < (left + mpDist)) And ((r = right) Or (Compare(input[l], input[r], sOn) = input[l]))) cache[i] = input[l] l += 1 Else cache[i] = input[r] r += 1 Endif Next For Local i:Int = left Until right input[i] = cache[i - left] Next End End