Daily Algorithms - 2/14/19
Posted by Admin_Ray
12 months ago
console.log("Happy Valentine's Day!");
1
12 months ago
Merge Sort is a recursive algorithm from the Divide and Conquer paradigm where problems are programmatically broken down and reassembled to yield a final solution.  Merge Sort takes a list and halves it until all the elements are single pieces and then iteratively sorts them at each level.  The final result is a perfectly sorted list.  The time complexity is O(n log(n)) which isn't ideal but is much better than the otherwise quadratic complexity O(n^2) traditional sorting methods require.

Here's how to implement MergeSort in Python.

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
1
NUMBER FOLLOWERS
A community for programmers (or non-programmers) to come together and let out their inner nerd.

if (user.type === "programmer" || user.type === "normie") {
  console.log(`Welcome, ${user.username}!`);
}
COMMUNITY RULES
  • 1. Anything goes.
COMMUNITY MODERATORS
None