This code implements the Merge Sort.
I'll post this at Rosetta Code, after it's vetted here.
#NoEnv
Test := []
Loop 100 {
Random n, 1, 1000
Test.Insert( n )
}
Result := MergeSort( Test )
Loop % Result.MaxIndex() {
MsgBox, 1, , % Result[A_Index]
IfMsgBox Cancel
Break
}
Return
/*
Function MergeSort
Sorts an array by first recursively splitting it down to its
individual elements and then merging those elements in their
correct order.
Parameters
Array The array to be sorted
Returns
The sorted array
*/
MergeSort( Array )
{
; Return single element arrays
If ( ! Array.HasKey( 2 ) )
Return Array
; Split array into Left and Right halfs
Left := []
Right := []
Middle := Array.MaxIndex() // 2
While ( Array.MaxIndex() )
If ( A_Index <= Middle )
Left.Insert( Array.Remove( 1 ) )
Else
Right.Insert( Array.Remove( 1 ) )
; Recurse into Left and Right
Left := MergeSort( Left )
Right := MergeSort( Right )
Return ___Merge( Left, Right )
}
/*
Function ___Merge
Merges two sorted arrays so that the result is sorted
Parameters
Left The first array
Right The second array
Returns
The sorted merging of Left and Right
*/
___Merge(Left, Right)
{
Result := []
; If all the Right values are greater than all the
; Left values, just append Right at the end of Left.
If ( Left[Left.MaxIndex()] <= Right[1] ) {
While ( Right.MaxIndex() )
Left.Insert( Right.Remove( 1 ) )
Return Left
}
; Loop until one of the arrays is empty
While( Left.MaxIndex() and Right.MaxIndex() )
If ( Left[1] <= Right[1] )
Result.Insert( Left.Remove( 1 ) )
Else
Result.Insert( Right.Remove( 1 ) )
While ( Left.MaxIndex() )
Result.Insert( Left.Remove( 1 ) )
While ( Right.MaxIndex() )
Result.Insert( Right.Remove( 1 ) )
Return Result
} Hopefully this will inspire others to update Rosetta Code using AHK_L syntax.
_________________________
Composed/Posted with WYSIWYG BBCode Editor
