Merge Sort¶

Tags: Recursion, Divide & Conquer

In [41]:

import numpy as np

# from time_sorting_algorithm import run_sorting_algorithm
from random import randint

import numpy as np # from time_sorting_algorithm import run_sorting_algorithm from random import randint

In [42]:

unsorted_list = np.arange(0, 10)
np.random.shuffle(unsorted_list)
print(unsorted_list)

unsorted_list = np.arange(0, 10) np.random.shuffle(unsorted_list) print(unsorted_list)

[7 0 3 2 1 8 5 4 6 9]

In [48]:

sample_arr = [8, 2, 6, 4, 5]

sample_arr = [8, 2, 6, 4, 5]

In [49]:

def merge(left, right):

    # did not understand the below conditions
    if len(left) == 0:
        print("NEVER HERE")
        return right

    if len(right) == 0:
        return left

    left_idx = right_idx = 0
    result = []

    # understood
    while len(result) < len(left) + len(right):

        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

        if left_idx == len(left):
            result += right[right_idx:]
            break

        if right_idx == len(right):
            result += left[left_idx:]
            break

    return result

def merge(left, right): # did not understand the below conditions if len(left) == 0: print("NEVER HERE") return right if len(right) == 0: return left left_idx = right_idx = 0 result = [] # understood while len(result) < len(left) + len(right): if left[left_idx] <= right[right_idx]: result.append(left[left_idx]) left_idx += 1 else: result.append(right[right_idx]) right_idx += 1 if left_idx == len(left): result += right[right_idx:] break if right_idx == len(right): result += left[left_idx:] break return result

In [50]:

def partition(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2

    left_sub_array = partition(arr[:mid])
    right_sub_array = partition(arr[mid:])
    return merge(left_sub_array, right_sub_array)

def partition(arr): if len(arr) < 2: return arr mid = len(arr) // 2 left_sub_array = partition(arr[:mid]) right_sub_array = partition(arr[mid:]) return merge(left_sub_array, right_sub_array)

In [51]:

partition(sample_arr)

partition(sample_arr)

Out[51]:

[2, 4, 5, 6, 8]

In [55]:

partition(list(unsorted_list))

partition(list(unsorted_list))

Out[55]:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [54]:

list(unsorted_list)

list(unsorted_list)

Out[54]:

[7, 0, 3, 2, 1, 8, 5, 4, 6, 9]