Code archives/Algorithms/Top-down merge sort for arrays

' 	--+-----------------------------------------------------------------------------------------+--
'	  |   This code was originally written by Sophie Kirschner (sophiek@pineapplemachine.com)   |  
' 	  | It is released as public domain. Please don't interpret that as liberty to claim credit |  
' 	  |   that isn't yours, or to sell this code when it could otherwise be obtained for free   |  
'	  |                because that would be a really shitty thing of you to do.                |
' 	--+-----------------------------------------------------------------------------------------+--

SuperStrict



' Example Code

Rem

Framework brl.standardio
Import brl.random

Const numnodes%=10

SeedRnd MilliSecs()

Type node
	Field value%=Rand(0,99)
	Method compare%(obj:Object)
		If value>node(obj).value Return 1
		Return -1
	End Method
End Type

Local nodearray:node[numnodes]
For Local i%=0 Until numnodes
	nodearray[i]=New node
Next

Print "~nArray before sorting:"
For Local i%=0 Until numnodes
	Print nodearray[i].value
Next

MergeSortArray(nodearray)

Print "~nArray after sorting:"
For Local i%=0 Until numnodes
	Print nodearray[i].value
Next

EndRem



' Top-down merge sort
' algorithm taken from: http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

Function MergeSortArray(array:Object[],ascending%=True,comparefunc(o1:Object,o2:Object)=_Array_CompareObjects)
	Local buffer:Object[]=New Object[array.length]
	_MergeSortAtoA array,buffer,0,array.length,comparefunc,ascending
End Function

Function _MergeSortAtoA(a:Object[],b:Object[],ll%,rr%,comparefunc(o1:Object,o2:Object),ascending%)
	If rr-ll>=2 Then
		Local mm%=(ll+rr)/2
		_MergeSortAtoB a,b,ll,mm,comparefunc,ascending
		_MergeSortAtoB a,b,mm,rr,comparefunc,ascending
		_MergeSortMerge b,a,ll,mm,rr,comparefunc,ascending
	EndIf
End Function

Function _MergeSortAtoB(a:Object[],b:Object[],ll%,rr%,comparefunc(o1:Object,o2:Object),ascending%)
	If rr-ll>=2 Then
		Local mm%=(ll+rr)/2
		_MergeSortAtoA a,b,ll,mm,comparefunc,ascending
		_MergeSortAtoA a,b,mm,rr,comparefunc,ascending
		_MergeSortMerge a,b,ll,mm,rr,comparefunc,ascending
	ElseIf rr-ll=1
		b[ll]=a[ll]
	EndIf
End Function

Function _MergeSortMerge(a:Object[],b:Object[],ll%,mm%,rr%,comparefunc(o1:Object,o2:Object),ascending%)
	Local l%=ll,r%=mm
	Local comparetarg%=1-ascending*2
	For Local o%=ll Until rr
		If r>=rr Or ((l<mm) And (comparefunc(a[l],a[r])=comparetarg)) Then ' a[l]<=a[r]
			b[o]=a[l]
			l:+1
		Else
			b[o]=a[r]
			r:+1
		EndIf
	Next
End Function

Function _Array_CompareObjects%(o1:Object,o2:Object)
	Return o1.Compare(o2)
End Function