Mergesort a linked list/Code Snippet (SoCoder)

Created 26 August 2009 | Last Edited 26 August 2009)
Mergesort a linked list by HoboBen | No Votes
Mergesort is a sorting algorithm that is especially suited to sorting linked lists.

Note: You really, really don't want to sort any lists that contain strings!!!

Feel free to use for any purpose, with or without attribution.
{
    Mergesort a linked list example
    Updated 20090826
    
    By Ben Golightly
    www.tophatstuff.co.uk
    www.funr.co.uk
    
    Note: You really, really don't want to sort any lists that contain strings!!!
}

Program
    Uses
        pure2d,
        keyset

Const
    // Set mode to 1 for Random inital sort
    // Set mode to 2 for worst-case inital sort
    // Set mode to 3 for best-case inital sort
    
    mode = 1
    
    NUMBER_OF_ITEMS = 10000 // That's 10,000

Type items = Record
    index: Integer
    //foo: String
    bar: Integer
    baz: Boolean
EndType

Var
    itemList: List of items
    anItem: ^items


Procedure MergeSort(ByRef itemList: List of items)
Var
    item1: ^items
    item2: ^items
    
    itemLast: ^items
    itemFirst: ^items
    
    tResult : List of items
    tLeft : List of items
    tRight: List of items
    
    i, count, middle: Integer
Begin

    count = CountList(itemList)
    If count <= 1 then exit
    middle = (count / 2) - 1 

    Loop item1 through itemList
        
        If i <= middle then
            item2 = NewItem(tLeft)
            Cloneitem(item1, item2)
        Else
            item2 = NewItem(tRight)
            Cloneitem(item1, item2)
        Endif
        
        Inc(i)    
    EndLoop
    
    MergeSort(tLeft)
    MergeSort(tRight)
    
    itemLast = LastItem(tLeft)
    itemFirst = FirstItem(tRight)
    
    If itemLast.index > itemFirst.index
         MergeSort_merge(tResult, tLeft, tRight)
    Else
         Loop item1 through tLeft
            item2 = NewItem(tResult)
            Cloneitem(item1, item2)
            Free(item1)
         EndLoop
         Loop item1 through tRight
            item2 = NewItem(tResult)
            Cloneitem(item1, item2)
            Free(item1)
         EndLoop
    Endif    
    
    // return result
    Loop item1 through itemList
        Free(item1)
    EndLoop
    
    Loop item1 through tResult
        item2 = NewItem(itemList)
        Cloneitem(item1, item2)
        Free(item1)
    EndLoop

End


Procedure MergeSort_merge(ByRef tResult: List of items, ByRef tLeft: List of items, ByRef tRight: List of items)
Var
    item1, item2 : ^items
    itemFirst1 : ^items
    itemFirst2 : ^items
Begin

    While ( (CountList(tLeft) > 0) and (CountList(tRight) > 0) )

        itemFirst1 = FirstItem(tLeft)
        itemFirst2 = FirstItem(tRight)
            
        If itemFirst1.index <= itemFirst2.index
            item1 = NewItem(tResult)
            Cloneitem(itemFirst1, item1)
            Free(itemFirst1)
        Else
            item1 = NewItem(tResult)
            Cloneitem(itemFirst2, item1)
            Free(itemFirst2)
        Endif
    Wend
    
    If (CountList(tLeft) > 0) 
         Loop item1 through tLeft
            item2 = NewItem(tResult)
            Cloneitem(item1, item2)
            Free(item1)
         EndLoop
    Else  
         Loop item1 through tRight
            item2 = NewItem(tResult)
            Cloneitem(item1, item2)
            Free(item1)
         EndLoop
    Endif
    
End

Procedure Cloneitem(item1: ^items, item2: ^items)     
Begin

    { item 2 }
    item2.index = item1.index
    //item2.foo = item1.foo
    item2.bar = item1.bar
    item2.baz = item2.baz

End


Function RandomString() : String
Begin
    Case (Rand(1, 9)) of
        1: result = "tea"
        2: result = "coffee"
        3: result = "beer"
        4: result = "wine"
        5: result = "rum"
        6: result = "water"
        7: result = "vodka"
        8: result = "orange juice"
        9: result = "apple juice" 
    EndCase
End

Var
    i: Integer
    ms: Integer

Begin

    // Create some example items...
    
    For i = 0 to NUMBER_OF_ITEMS
    
        anItem = NewItem(itemList)
        
        Case mode of
            1: anItem.index = Rand(1, 100000)
            2: anItem.index = 10000 - i
            3: anItem.index = i
        EndCase
        
        //anItem.foo = RandomString()
        anItem.bar = Rand(1, 1000)
        anItem.baz = TRUE
        
    Next


    
    OpenScreen(800, 600, 32, FALSE)
    

    // Before     
    For i = 3 to 40
                  
        anItem = IndexedItem(itemList, i)
        Text(10, i*14, "Item index="+anItem.index+" bar="+anItem .bar)
    
    Next
    Text(10, 10, "Press Enter to sort "+NUMBER_OF_ITEMS+" items.")
    
    While (KeyHits(VK_RETURN) < 1)
        Flip
        Pause(1)
    Wend
    Cls
    Flip
    
    
    ms = Millisecs
    MergeSort(itemList)
    ms = Millisecs - ms
    

    // After     
    For i = 3 to 40
                  
        anItem = IndexedItem(itemList, i)
        Text(10, i*14, "Item index="+anItem.index+" bar="+anItem .bar)
    
    Next
    Text(10, 10, "Sorted "+NUMBER_OF_ITEMS+" items in "+ms+" millisecs. Press Enter to quit.")
    
    While (KeyHits(VK_RETURN) < 1)
        Flip
        Pause(1)
    Wend

End
-->

Code for the Cobra programming language.
There are no comments for this entry.