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)