![]() |
| Merge Sort Algorithm |
We will implement merge sort program in python. Merge sort is an O(n log n) comparison-based sorting algorithm.
Merge sort
is a divide and conquer algorithm. Divide and conquer algorithms
divide the original data into smaller sets of data to solve the problem.
Conceptually, merge
sort works as follows in recursive fashion:
1. Divide Step
If a given array A has zero elements or one element then it simply returns; it is already sorted. Otherwise, partition the n-element sequence to be sorted into two subsequences of n/2 elements each.
2. Conquer Step
If a given array A has zero elements or one element then it simply returns; it is already sorted. Otherwise, partition the n-element sequence to be sorted into two subsequences of n/2 elements each.
2. Conquer Step
Sort the divided
subsequences recursively using the Merge Sort.
3. Combine Step
Combine or merge the divided sorted subsequences, each to generate the sorted array consisting of n elements.
3. Combine Step
Combine or merge the divided sorted subsequences, each to generate the sorted array consisting of n elements.
The Logic of Merge Sort goes as
follows:
- When the array consists of only one element do nothing, because it is already sorted.
- Find the middle point of array (or mid points when you want to split into more parts).
- Recursively Merge Sort part of array from the start to the middle point.
- Recursively Merge Sort part of array above the middle point.
- Merge (join) both sorted parts.
Python Source Code for merge sort
def mergeSort(alist):
if len(alist)>1:
mid = len(alist)/2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i,j,k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
alist = [5,1,4,2,3,7]
mergeSort(alist)
print(alist)
https://github.com/nitesh4u/MergeSortPython
