Merge Sort is a sorting algorithm which is based on divide and conquer approach. The list is divided into two halves until each sublist has a single element, and the sublists are merged in a sorted manner that the sorted list is obtained. It is a very efficient algorithm for sorting. The technique simply involves: Divide the list into two subslists, Make recursion call for the sublists, and then Merge the sublists.
Illustration:
Algorithm:
if length(list)>1
find point of divide,mid=length(list)//2
left sublist L,index 0 to mid
right sublist R, index mid+1 to length(list)-1
recursion,calling function itself for L
recursion,calling function itself for R
i=j=k=0
while i<length(L) and j<length(R)
if L[i] < R[j],then list[k]=L[i] and i=i+1
else, list[k]=R[j] and j=j+1
k=k+1
while i<length(L)
list[k]=L[i]
update i=i+1 and k=k+1
while i<length(R)
list[k]=R[j]
update j=j+1 and k=k+1
Time Complexity:
- Worst Case: O(nlogn)
- Average Case: O(nlogn)
- Best Case: O(nlogn)
Space Complexity: O(n)
Program for Merge Sort:
Ouput:
