//              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