Merge Sort Help

[Dirac]

EDIT: Issue Fixed. i'll upload this as a resource soon

I'm trying to code MergeSort using linked lists (better performance)

So i have this module that you can implement into your struct replacing the allocation methods, so far it only supports 1 linked list for the entire struct, I'll work on multiple merges when i finish this one.
NOTE: so far it's broken, need to know why

library MergeSort

    module MS
        static thistype array recycle
        static thistype       size =0
        
        static thistype array next
        static thistype array prev
        
        static method allocate takes nothing returns thistype
            local thistype this
            
            //*********************************************************************
            //  Always increment the size, this won't cause issues. This allocation
            //  method is similar to Alloc + linked list config.
            set size=size+1
            if 0==recycle[0] then
                set this=size
            else
                set this=recycle[0]
                set recycle[0]=recycle[recycle[0]]
            endif
            
            //*********************************************************************
            //  Places the instance inside a linked list.
            set prev[next[0]]=this
            set next[this]=next[0]
            set next[0]=this
            set prev[this]=0
            return this
        endmethod
        
        method deallocate takes nothing returns nothing
        
            //*********************************************************************
            //  Throws the instance to the recycle stack and reduce the list's size
            set recycle[this]=recycle[0]
            set recycle[0]=this
            set size=size-1
            
            //*********************************************************************
            //  Remove the instance from the linked list.
            set next[prev[this]]=next[this]
            set prev[next[this]]=prev[this]
        endmethod
        
        //*********************************************************************
        //  Ok this method is entitled to split and merge constatly until there
        //  is nothing left to split.
        private static method split takes integer start, integer end, integer count returns integer
            local integer half=start
            local integer r=0
            local integer p=0
            local integer s=0
            
            //*********************************************************************
            //  If the last node (end) of the list is equal to the first node
            //  (start) then skip.
            if start==end then
                return start
            endif
            
            //*********************************************************************
            //  Looks for the value placed at the half of the list.
            loop
                exitwhen s>=count/2
                set s=s+1
                set half=next[half]
            endloop
            
            //*********************************************************************
            //  Now it calls this function again but for each half (from start up
            //  to the previous node from the half and from the half up to the end)
            set start=split(start,prev[half],count/2)
            set half=split(half,end,(count+1)/2)
            
            //*********************************************************************
            //  Merges the list using 2 pointers: start and half.
            loop
                exitwhen start==next[end] or half==next[end] or start==half
                if compare(start,half) then
                    //*********************************************************************
                    //  If the pointers pass the compare method it means that the half node
                    //  needs to be placed behind the start node.
                    set s=next[half]
                    
                    //*********************************************************************
                    //  So we remove the half node from the list...
                    set next[prev[half]]=next[half]
                    set prev[next[half]]=prev[half]
                    
                    //*********************************************************************
                    //  ...and place it behind the start node.
                    set next[prev[start]]=half
                    set prev[half]=prev[start]
                    set prev[start]=half
                    set next[half]=start
                    
                    //*********************************************************************
                    //  keeps track of the previous half
                    if 0==r then
                        set r=half
                    endif
                    //*********************************************************************
                    //  After that we need half to point towards the node that was
                    //  previously pointing next[half] before, that's why i stored it
                    //  inside "s" and now retreive it.
                    set half=s
                else
                    //*********************************************************************
                    //  keeps track of the previous half
                    if 0==r then
                        set r=start
                    endif
                    
                    //*********************************************************************
                    //  If the value doesn't pass the compare method it means there's no
                    //  need for moving (the list is fine) and moves along
                    set start=next[start]
                endif
            endloop
            return r
        endmethod
        
        //*********************************************************************
        //  Next[0] is the first value from the list and Prev[0] the last.
        static method Sort takes nothing returns nothing
            call split(next[0],prev[0],size)
        endmethod
    endmodule
    
endlibrary

Example on how it works:
We're trying to sort the following list by the value their node has.
[ljass]0 - 3 - 5 - 6 - 1 - 4 - 9 - 8 - 0[/ljass]
Being "0" the head.

So we call the Sort static method

static method Sort takes nothing returns nothing
    call split(next[0],prev[0],size)
endmethod

Next[0] is now equal to 3
Prev[0] is now equal to 8
size is now equal to 7 (numbers in the list)

So now the split method will try to find the node in the middle of the list by moving a pointer forward until a variable that starts from 0 reaches the half of the count (7)

loop
    exitwhen s>=count/2
    set s=s+1
    set half=next[half]
endloop

[ljass]3 - 5 - 6 - 1 - 4 - 9 - 8[/ljass]
[ljass]--> --> --> ^[/ljass]
half is now equal to 1

the split method is now called for the starting value (3) and the value previous from the half (6) and also called for the half (1) to the last value of the list (8) and the count or size of both lists was now reduced by half
first call:
[ljass]3 - 5 - 6[/ljass] (count)==3
second call:
[ljass]1 - 4 - 9 - 8[/ljass] (count)==4

Since the first call is the one to be analyzed first we will take that way
Ok again the function attempts to find the half value of the list, and returns...
[ljass]3 - 5 - 6[/ljass]
[ljass]--> ^[/ljass]
5 is the half, the list needs to be splited again.

first call:
[ljass]3[/ljass] (count)==1
second call:
[ljass]5 - 6[/ljass] (count)==2

since the starting value of the list is equal to the last value of the list in the first call then the function is skipped. Half currently points towards 6.

if start==end then
    return start
endif

The second call will also be splitted, but would return 2 lists in which the start is equal to the end so they will be skipped too, now we move on to the second part of the function.

loop
    exitwhen start==next[end] or half==next[end] or start==half
    if compare(start,half) then
        //*********************************************************************
        //  If the pointers pass the compare method it means that the half node
        //  needs to be placed behind the start node.
        set s=next[half]
        
        //*********************************************************************
        //  So we remove the half node from the list...
        set next[prev[half]]=next[half]
        set prev[next[half]]=prev[half]
        
        //*********************************************************************
        //  ...and place it behind the start node.
        set next[prev[start]]=half
        set prev[half]=prev[start]
        set prev[start]=half
        set next[half]=start
        
        //*********************************************************************
        //  keeps track of the previous half
        if 0==r then
            set r=half
        endif
        //*********************************************************************
        //  After that we need half to point towards the node that was
        //  previously pointing next[half] before, that's why i stored it
        //  inside "s" and now retreive it.
        set half=s
    else
        //*********************************************************************
        //  keeps track of the previous half
        if 0==r then
            set r=start
        endif
        
        //*********************************************************************
        //  If the value doesn't pass the compare method it means there's no
        //  need for moving (the list is fine) and moves along
        set start=next[start]
    endif
endloop

Compares start (5) and half (6) and since their order is correct (smallest to greatest) doesn't pass the compare method and goes down to the part where it says [ljass]set start=next[start][/ljass] now start points towards 6 and half towards 6. And since [ljass]exitwhen start==half[/ljass] then the loop breaks. Now this call ended and returns "r" which is now equal to 5.
[ljass]3 - 5 - 6[/ljass]
Remember that in this list half is now equal to the return of the second call (r) which was 5.
compares start (3) with half (5) and since their order is correct then start moves 1 step forward, now we have that start is equal to end and the loop breaks, returns 3 (since this function was considered a "first call" then this return will be equal to the start of the previous call).

Ok now we proceed to the second call of the main list... remember? We look for the half...
[ljass]1 - 4 - 9 -8[/ljass] (count)==4
[ljass]--> --> ^[/ljass]
Splits the list.
first call:
[ljass]1 - 4[/ljass] (count)==2
second call
[ljass]9 - 8[/ljass] (count)==2

First call is in order, we'll skip that, move on to the second, start is equal to 9 and half equal to 8.
The order is incorrect, we have to put half (8) behind start (9)...

//*********************************************************************
//  If the pointers pass the compare method it means that the half node
//  needs to be placed behind the start node.
set s=next[half]

//*********************************************************************
//  So we remove the half node from the list...
set next[prev[half]]=next[half]
set prev[next[half]]=prev[half]

//*********************************************************************
//  ...and place it behind the start node.
set next[prev[start]]=half
set prev[half]=prev[start]
set prev[start]=half
set next[half]=start

//*********************************************************************
//  keeps track of the previous half
if 0==r then
    set r=half
endif
//*********************************************************************
//  After that we need half to point towards the node that was
//  previously pointing next[half] before, that's why i stored it
//  inside "s" and now retreive it.
set half=s

Ends the function and returns r (8)
We now return to the previous list
[ljass]1 - 4 - 8 - 9[/ljass] (count)==4
And half is pointing towards 8, but this list appears to be in order, so we'll skip the comparing process and assume that after that "r" was equal to 1 and returns it.
We got our full list now!
[ljass]0 - 3 - 5 - 6 - 1 - 4 - 8 - 9 - 0[/ljass]
start is equal to 3 and half is equal to 1
We begin now the long comparing process.
1. Compares (3) with (1), incorrect order, puts (1) behind (3) and half is now equal to 4
[ljass]0 - 1 - 3 - 5 - 6 - 4 - 8 - 9 - 0[/ljass]
2. Compares (3) with (4), correct order, start steps forwards and is now equal to 5
3. Compares (5) with (4), incorrect order, puts (4) behind (5) and half is now equal to 8
[ljass]0 - 1 - 3 - 4 - 5 - 6 - 8 - 9 - 0[/ljass]
4. Compares (5) with (8), correct order, start steps forwards and is now equal to 6
5. Compares (6) with (8), correct order, start steps forwards and is now equal to 8
Now start is equal to half and the loop ends. The list is now in correct order!
[ljass]0 - 1 - 3 - 4 - 5 - 6 - 8 - 9 - 0[/ljass]
However the editor returns
[ljass]0 - 1 - 4 - 5 - 3 - 6 - 8 - 9 - 0[/ljass]

Here's the demo for the test

struct tester extends array
    
    integer value
    private static method compare takes thistype v1, thistype v2 returns boolean
        return v1.value<v2.value
    endmethod
    
    implement MS
    
    private static method onInit takes nothing returns nothing
        local thistype this
        set allocate().value=8
        set allocate().value=9
        set allocate().value=4
        set allocate().value=1
        set allocate().value=6
        set allocate().value=5
        set allocate().value=3
        call Sort()
        set this=prev[0]
        loop
            exitwhen 0==this
            call BJDebugMsg(I2S(this.value))
            set this=prev[this]
        endloop
    endmethod
endstruct

EDIT:
Another very simplified example (greatest to smallest)

"-"     link union
"()"    half
"^"     start
"|"     split

3 - 5 - 6 -(1)- 4 - 9 - 8

3 -(5)- 6 | 1 - 4 -(9)- 8

3 | 5 -(6)| 1 -(4)| 9 -(8)
    ^       ^       ^
3 -(6)- 5 | 4 - 1 -(9)- 8
^           ^
6 - 3 -(5)| 9 - 4 - 1 -(8)
    ^           ^
6 - 5 -(3)| 9 - 8 - 4 - 1
        ^           ^
6 - 5 - 3 -(9)- 8 - 4 - 1
^
9 - 6 - 5 - 3 -(8)- 4 - 1
    ^
9 - 8 - 6 - 5 - 3 -(4)- 1
            ^
9 - 8 - 6 - 5 - 3 -(4)- 1
                ^
9 - 8 - 6 - 5 - 4 - 3 -(1)
                    ^
9 - 8 - 6 - 5 - 4 - 3 -(1)
                        ^