// Merge Sort [GUI Friendly] v1.01
// by Flux
// http://www.hiveworkshop.com/forums/members/flux/
//
// Merge Sort is an efficient sorting algorithm
// that has a worst case performance of O(n logn)
// This system allows you to sort values of an array
// in either ascending or descending order
// Additionally, it this system allows you to get the
// sorted indices of the array values.
//
// Purely written in JASS and doesn't require anything
function MSort_Display takes nothing returns nothing
local integer i = udg_MSort_StartIndex
call BJDebugMsg("========== |cffffcc00[Merge Sort]:|r Data ===============")
loop
exitwhen i > udg_MSort_EndIndex
call BJDebugMsg("MSort_Values[" + I2S(i) + "] = " + R2S(udg_MSort_Values[i]) + ", MSort_Indices[" + I2S(i) + "] = " + I2S(udg_MSort_Indices[i]))
set i = i + 1
endloop
call BJDebugMsg("============== End Display =================\n")
endfunction
function MSort_Merge takes integer leftStart, integer leftEnd, integer rightStart, integer rightEnd returns nothing
local integer i = leftStart
local integer j = rightStart
local integer k = i
loop
exitwhen i > leftEnd or j > rightEnd
if udg_MSort_Ascending then
if udg_MSort_Left[i] < udg_MSort_Right[j] then
set udg_MSort_Values[k] = udg_MSort_Left[i]
set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
set k = k + 1
set i = i + 1
else
set udg_MSort_Values[k] = udg_MSort_Right[j]
set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
set k = k + 1
set j = j + 1
endif
else
if udg_MSort_Left[i] > udg_MSort_Right[j] then
set udg_MSort_Values[k] = udg_MSort_Left[i]
set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
set k = k + 1
set i = i + 1
else
set udg_MSort_Values[k] = udg_MSort_Right[j]
set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
set k = k + 1
set j = j + 1
endif
endif
endloop
//Fill up remaining
loop
exitwhen i > leftEnd
set udg_MSort_Values[k] = udg_MSort_Left[i]
set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
set k = k + 1
set i = i + 1
endloop
loop
exitwhen j > rightEnd
set udg_MSort_Values[k] = udg_MSort_Right[j]
set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
set k = k + 1
set j = j + 1
endloop
//Update IndexInitial
set i = leftStart
loop
exitwhen i == k
set udg_MSort_IndexInitial[i] = udg_MSort_Indices[i]
set i = i + 1
endloop
endfunction
//Recursive Function
function MSort_Merge_Sort takes integer start, integer end returns nothing
local integer i = start
local integer mid
if end - start >= 1 then
set mid = (end + start)/2
call MSort_Merge_Sort(start, mid)
call MSort_Merge_Sort(mid+1, end)
loop
exitwhen i > mid
set udg_MSort_Left[i] = udg_MSort_Values[i]
set i = i + 1
endloop
loop
exitwhen i > end
set udg_MSort_Right[i] = udg_MSort_Values[i]
set i = i + 1
endloop
call MSort_Merge(start, mid, mid+1, end)
//call MSort_Display()
// ^uncomment to display values
endif
endfunction
function Trig_Merge_Sort_Main takes nothing returns boolean
call MSort_Merge_Sort(udg_MSort_StartIndex, udg_MSort_EndIndex)
return false
endfunction
//===========================================================================
function InitTrig_Merge_Sort takes nothing returns nothing
set gg_trg_Merge_Sort = CreateTrigger()
call TriggerAddCondition(gg_trg_Merge_Sort, Condition(function Trig_Merge_Sort_Main))
endfunction