Merge Sort with LinkedLists

12-13-2008, 08:19 PM

I wrote this up quick last night however when I was doing more thorough testing this morning I've discovered it fails when the list is ~> 60 or so, after an hour of tinkering around I can't find my mistake, could anyone help me out here?

JASS:

    private function merge takes List l1, List l2 returns List
        local List mergedList = List.create()
        local Link tempLink
        local Data d1
        local Data d2
        
        set tempLink = l1.first
        loop
            exitwhen (l1.size <= 0) or (l2.size <= 0)
            set d1 = l1.first.data
            set d2 = l2.first.data

            if (d1.value <= d2.value) then
                call Link.createLast(mergedList, d1)
                call l1.first.destroy()
            else
                call Link.createLast(mergedList, d2)
                call l2.first.destroy()
            endif
        endloop
        
        set tempLink = l1.first
        loop
            exitwhen tempLink == 0
            set d1 = tempLink.data
            call Link.createLast(mergedList, d1)
            set tempLink = tempLink.next
        endloop
        
        set tempLink = l2.first
        loop
            exitwhen tempLink == 0
            set d1 = tempLink.data
            call Link.createLast(mergedList, d1)
            set tempLink = tempLink.next
        endloop

        return mergedList
    endfunction
    
    private function merge_sort takes List l returns List
        local List left = List.create()
        local List right = List.create()
        local List result = List.create()
        local Link tempLink
        local Data d
        local integer m = 0
        local integer i = 0
        
        if (l.size <= 1) then
            return l
        else
            set m = l.size / 2
        endif

        set i = 0
        set tempLink = l.first
        loop
            exitwhen tempLink == 0
            set d = tempLink.data
            if (i < m) then
                //add to left
                call Link.createLast(left, d)
            else
                //add to right
                call Link.createLast(right, d)
            endif

            set tempLink = tempLink.next
            set i = i + 1
        endloop

        set left = merge_sort(left)        
        set right = merge_sort(right)
        
        set result = merge(left, right)
        
        return result
    endfunction

12-13-2008, 08:27 PM

Ammorth

What do you need the merge sort for?

Reason I ask is that I was going to include a merge sort in my LinkedList script until I realized there is no need to do so. It is much easier and efficient to insert the data in order than to insert and then sort. Also, if the data changes, it is more efficient to remove and re-insert in order than to merge sort the entire list again.

I would guess that the reason why it fails is cause you are reaching the OP limit with such a large list. If you really want to use merge sort, look at a way to use O(1) data space and without recursion. I'll get you some links in a second.

http://fanf.livejournal.com/40178.html a great explanation for getting an efficient merge sort with linked lists

http://www.wc3campaigns.net/pastebin...916a5bc65141df this was my LinkedList version 1.1 that I wrote and never released. After writing it, with a little help from Anitarf, I realized it was too big and complicated for something that was supposed to be simple and elegant.

I did end up writing a modified version of sort in that script that was O(1), but I'm not sure if I kept it.

12-13-2008, 08:31 PM

hitokirixeno

Quote:

Originally Posted by Ammorth

I tag units in my map with a list of integers that correspond to abilities, but yeah now that you mention it, it's probably a better idea to insert in the proper location rather than sorting the entire list. Thanks for the input.