Tuesday, January 6, 2015

Mergesort

English
Recursively sort the left and right side of the array, and then merge the results by looping through and picking the smallest element remaining during each iteration.

This is a divide and conquer algorithm. It breaks the problem down into many smaller, easier problems. 

Psuedocode
Sort(array, left, right)
{
   If right <= left return

   mid = left + (right - left)/2 

    Sort(array, left, mid)
    Sort(array, mid+1, right)
    Merge(array, left, mid, right)

}

Merge(array, left, mid, right)
{
    Copy array to auxiliary array from left to right

    LeftPtr = left
    RightPtr = mid+1

    Loop through the auxiliary array from left to right
        Compare auxiliary[leftPtr] with auxiliary[rightPtr]
        Whichever one is bigger, or if there are none left on one side, put it in the array[loopIndex]
        Increment LeftPtr/rightPtr depending on which side got taken 

}

No comments:

Post a Comment

There was an error in this gadget