We will look at the Merge Sort Algorithm which is used to sort an unsorted list. The input list is divided into two parts and they are solved recursively and then they are merged.
Worst Case Time Complexity: O(n log n)
Worst Case Space Complexity: O(n)
Merge sort is a divide and conquer algorithm.
1. We are given an unsorted list of n numbers
2. Divide it into two array of equal size
3. Again Divide those two into another two array of equal size
4. Keep on dividing it until one element is left in each array.
5. Keep Merging the sub arrays to produce sorted arrays until there is only one array remaining.. This will be our sorted array.
def Merge(left,right,A):
i=j=k=0
while(i < len(left) and j < len(right)):
if(left[i] < right[j]):
A[k]=left[i] i+=1
else:
A[k]=right[j] j+=1
k+=1
while(i < len(left)):
A[k]=left[i] i+=1
k+=1
while(j < len(right)):
A[k]=right[j] j+=1
k+=1
def MergeSort(A):
left = [] right = [] n = len(A)
if(n<2):
return
mid = n/2
for i in range(mid):
left.append(A[i])
for i in range(mid,n):
right.append(A[i])
MergeSort(left)
MergeSort(right)
Merge(left,right,A)
A = [2,4,1,3,8,9,0,-2,-1] #given unsorted array
MergeSort(A)
print A
You can take this Python Quiz