minte9
LearnRemember   ALGORITHMS





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 quicksort(items, i=0, j=None):
    if j == None: 
        j = len(items) - 1

    if i > j: 
        return # Base case
    
    pivot = items[j]
    for k in range(i, j + 1):

        if items[k] < pivot:
            items[i], items[k] = items[k], items[i] # swap items
            i = i + 1 # move pointer

        if items[k] == pivot:
            items[i], items[k] = items[k], items[i] # move pivot
    
    quicksort(items, 0, i - 1) # sort left partition
    quicksort(items, i + 1, j) # sort right partition

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


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

start, end = 0, 0
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: