Merge Sort

Code

Here is the pseudo-code for merging 2 sorted arrays into one:

def merge_2_arr(a1,a2):
final = []
l1 = len(a1)
l2 = len(a2)
h1 = 0
h2 = 0
while h1 < l1 and h2 < l2:
if a1[h1] < a2[h2]:
final.append(a1[h1])
h1 += 1
else:
final.append(a2[h2])
h2 += 1

if h1 < l1:
for i in range(h1,l1):
final.append(a1[i])

elif h2 < l2:
for i in range(h2,l2):
final.append(a2[i])

return final
def merge_sort(a):
if len(a) == 1:
return a
middle = int(len(a)/2)
a1 = merge_sort(a[0:middle])
a2 = merge_sort(a[middle:])
final = merge_2_arr(a1,a2)
return final

Complexity Analysis

We want to find how many operations this algorithm takes to sort an array of length n. We will cover this in the next write-up. See you soon!!!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store