Programming

  minte9
LearnRemember



Divide Conquer / Merge Sort

Merge Sort

Each recusive call divides the unsorted list into halves. 
 
""" Merge sort / Algorithm
Each recusive call divides the unsorted list into halves, 
dowm into lists of zero of one lengths.

Then, as the recursive calls return, these smaller lists 
are merged toghether into sorted order.
"""

def merge_sort(items, depth=0):

    if len(items) <= 1: # Base case
        return items

    m = len(items) // 2
    L = merge_sort(items[:m], depth + 1) # Recursive
    R = merge_sort(items[m:], depth + 1)
    
    # At this stage left and right are sorted
    print(depth * " ", L, " ", R) 

    i = 0
    j = 0
    sorted = []
    while len(sorted) < len(items):

        # Append the smaller value and 
        # advance tge pointer to next item
        if L[i] < R[j]:
            sorted.append(L[i])
            i = i + 1
        else:
            sorted.append(R[j])
            j = j + 1

        # If one of the pointers has reached the end of its list,
        # put the rest of the other list into sorted list
        if i == len(L):
            sorted.extend(R[j:])
            break
        if j == len(R):
            sorted.extend(L[i:])
            break
    
    print(depth * " ", sorted) 
    return sorted

data = [2, 9, 8, 5, 3, 4, 7, 6]
print(data)

sorted = merge_sort(data)
print(sorted)

"""
    [2, 9, 8, 5, 3, 4, 7, 6]
       [2]   [9]
       [2, 9]
       [8]   [5]
       [5, 8]
      [2, 9]   [5, 8]
      [2, 5, 8, 9]
       [3]   [4]
       [3, 4]
       [7]   [6]
       [6, 7]
      [3, 4]   [6, 7]
      [3, 4, 6, 7]
     [2, 5, 8, 9]   [3, 4, 6, 7]
     [2, 3, 4, 5, 6, 7, 8, 9]
    [2, 3, 4, 5, 6, 7, 8, 9]
"""

Timer

Faster then quicksort, almost as fast as native sort(). 
 
""" Merge sort algorithm / Speed tests
"""

import random
import time
start, end = 0, 0

def timer(func):
    def wrapper(*args, **kwargs):
        global start, end

        if start == 0: 
            start = time.time()

        result = func(*args, **kwargs)
        end = time.time()
        return result
        
    return wrapper

@timer
def merge_sort(items):
    if len(items) <= 1: # Base case
        return items
        
    m = len(items) // 2
    L = merge_sort(items[:m]) # Recursive
    R = merge_sort(items[m:])
    
    i = 0
    j = 0
    sorted = []
    while len(sorted) < len(items):

        if L[i] < R[j]:
            sorted.append(L[i])
            i = i + 1
        else:
            sorted.append(R[j])
            j = j + 1

        if i == len(L): sorted.extend(R[j:])
        if j == len(R): sorted.extend(L[i:])
    return sorted

@timer
def native_sort(items):
    return items.sort()


# Time
lst = random.sample(range(0, 300000), 300000)

start, end = 0, 0
sorted = merge_sort(lst)
t1 = end - start

start, end = 0, 0
native_sort(lst)
t2 = end - start

print("merge_sort() 300000 items:", t1, "s")
print("sort() 300000 items:", t2, "s")

"""
    merge_sort() 300000 items:  3.0545575618743896 s
    sort() 300000 items:        0.10179662704467773 s
"""




References