Merge Sort from Scratch in Python

Question

I built a merge sort in python just to have a more thorough understanding of how the algorithm works. What I have written works fine, but I assume there is room for improvement and ways to make my implementation more efficient.

I would appreciate any feedback or critiques!

"""
2019-10-17

This project simply re-creates common sorting algorithms
for the purpose of becoming more intimately familiar with 
them.
"""

import random
import math

#Generate random array
array = [random.randint(0, 100) for i in range(random.randint(5, 100))]
print(array)

#Merge Sort
def merge(array, split = True):
    split_array = []
    #When the function is recursively called by the merging section, the split will be skipped
    continue_splitting = False
    if split == True:
        #Split the array in half
        for each in array:
            if len(each) > 1:
                split_array.append(each[:len(each)//2])
                split_array.append(each[len(each)//2:])
                continue_splitting = True
            else:
                split_array.append(each)
    if continue_splitting == True:
        sorted_array = merge(split_array)
        #A return is set here to prevent the recursion from proceeding once the array is properly sorted
        return sorted_array
    else:
        sorted_array = []
        if len(array) != 1:
            #Merge the array
            for i in range(0, len(array), 2):
                #Pointers are used to check each element of the two mergin arrays
                pointer_a = 0
                pointer_b = 0
                #The temp array is used to prevent the sorted array from being corrupted by the sorting loop
                temp = []
                if i < len(array) - 1:
                    #Loop to merge the array
                    while pointer_a < len(array[i]) or pointer_b < len(array[i+1]):
                        if pointer_a < len(array[i]) and pointer_b < len(array[i+1]):
                            if array[i][pointer_a] <= array[i + 1][pointer_b]:
                                temp.append(array[i][pointer_a])
                                pointer_a += 1
                            elif array[i + 1][pointer_b] < array[i][pointer_a]:
                                temp.append(array[i + 1][pointer_b])
                                pointer_b += 1
                        #If the pointer is equal to the length of the sub array, the other sub array will just be added fully
                        elif pointer_a < len(array[i]):
                            for x in range(pointer_a, len(array[i])):
                                temp.append(array[i][x])
                                pointer_a += 1
                        elif pointer_b < len(array[i + 1]):
                            for x in range(pointer_b, len(array[i + 1])):
                                temp.append(array[i + 1][x])
                                pointer_b += 1
                else:
                    for each in array[i]:
                        temp.append(each)
                sorted_array.append(temp)
            if len(sorted_array) != 1:
                #Recursively sort the sub arrays
                sorted_array = merge(sorted_array, False)
    return sorted_array


sorted_array = merge([array])[0]
print()
print(sorted_array)

Answer 1

At the end of the code, it looks like merge() is called by nesting the array in a list and the result is the 0th element of the returned list. This is an unusual calling convention, is different than the way the built in sorted() is called, and it is not documented, which would likely lead to many errors. If this interface is needed for the algorithm to work, it would be better if merge() handled these details an then called another function. For example:

def merge(array):
    return _merge([array], True)

def _merge(array, True):
    ... same as your original code ...

The boolean argument split appears to control whether merge() splits the array into two smaller parts or merges two smaller parts together. This complicates the logic and makes it more difficult to follow. It would be better two have two separate functions.

It is also appears that the code takes parts of a recursive implementation and parts from an iterative implementation. For example, merge is called recursively to split the array into smaller arrays, but for i in range(0, len(array), 2): loops over a list of subarrays and merges them in pairs.

The essence of merge sort is: if the array isn't sorted, split it into two parts, sort both parts separately, and then merge the two parts together. Here is a recursive implementation:

def merge_sort(array):
    if is_not_sorted(array):
        # split array in two
        middle = len(array) // 2
        left_half = array[:middle]
        right_half = array[middle:]

        # sort each part
        left_half = merge_sort(left_half)
        right_half = merge_sort(right_half)

        array = merge_halves(left_half, right_half)
        return array

    else:
        # array is already sorted
        return array

Usually, if is_not_sorted(): is implemented as if len(array) > 1: (if there is more than one item in the array, it is presumed to be unsorted). But some implementations (like Python's builtin sorted or list.sort) check small lists to see if they are already sorted. Also, the two halves are usually sorted using a recursive call to merge_sort(), but some implementations may use a different sorting algorithm if the array is small.

merge_halves() is then basically the same as the while pointer_a < len(array[i])... loop in your code (with a few simplifications):

def merge_halves(left, right):
    merged_array = []
    pointer_a = 0
    pointer_b = 0
    while pointer_a < len(left) and pointer_b < len(right):
        if left[pointer_a] <= right[pointer_b]:
            merged_array.append(left[pointer_a])
            pointer_a += 1

        elif right[pointer_b] < left[pointer_a]:
            merged_array.append(right[pointer_b])
            pointer_b += 1

    #At the end of one subarray, extend temp by the other subarray
    if pointer_a < len(left):
        merged_array.extend(left[pointer_a:])

    elif pointer_b < len(right):
        merged_array.extend(right[pointer_b:])

    return merged_array

An iterative version might look something like this (code on the fly, so may have errors):

def merge(array):
    # make all the sub arrays 1 item long.  A more intelligent version might
    # split it into runs that are already sorted
    array = [[item] for item in array]

    while len(array) > 1:
        temp = []

        for i in range(0, len(array), 2):
            #Pointers are used to check each element of the two mergin arrays
            pointer_a = 0
            pointer_b = 0

            #Loop to merge the array
            while pointer_a < len(array[i]) and pointer_b < len(array[i+1]):
                if array[i][pointer_a] <= array[i + 1][pointer_b]:
                    temp.append(array[i][pointer_a])
                    pointer_a += 1

                else:
                    temp.append(array[i + 1][pointer_b])
                    pointer_b += 1

            if pointer_a < len(array[i]):
                temp.extend(array[i][x])

            elif pointer_b < len(array[i + 1]):
                temp.extend(array[i + 1][x])


        #there were an odd number of sub_arrays, just copy over the last one
        if len(sub_arrays) % 2:
            temp.append(sub_arrays[-1])

        array = temp

    return array[0]