merge_sort.py

#alright, 
#MERGE SORT basically involves recursive merging of smaller arrays to form sorted larger arrays


#so the most important step in implementing this in O(nlogn) is to make sure merging is done in O(n) and then there are O(logn) steps


# merging
# i'll need to create a resultant array that has len of a+b, assuming a and b are sorted
# then merge arrays by obtaining the minimum value from each array... obiously compare one comparison of leftmost element will help obtain that information

# maintain 2 indices for iterating each of them instead of popping the array



#done and works
def merge(a,b):
    n = len(a)+len(b) #len of new array c
    i,j=[0,0] #indices of 2 sub-arrays
    k=0 #index for new array c
    c = []

    for k in range(n):
        if a[i]<b[j]:
            c.append(a[i])
            i+=1
            if i==len(a):
                c.extend(b[j:len(b)])
                break
        else:
            c.append(b[j])
            j+=1
            if j==len(b):
                c.extend(a[i:len(a)])
                break
    return c


def sort(unsorted):
    a = len(unsorted)

    if(a==1):
        return unsorted
    if(a==2):
        if unsorted[0] < unsorted[1]:
            return unsorted
        else:
            return [unsorted[1],unsorted[0]]

    s1,s2 = (unsorted[:a//2],unsorted[a//2:a])
    s1=sort(s1)
    s2=sort(s2)
    return merge(s1,s2)


print(sort([1,5,5,2,1,6,8,34,21,5,7,8,3,12,41,2,45]))