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)
1 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]