Merge Sort in Python

Merge Sort Algorithm
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
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.

The Logic of Merge Sort goes as follows:

  1. When the array consists of only one element do nothing, because it is already sorted.
  2. Find the middle point of array (or mid points when you want to split into more parts).
  3. Recursively Merge Sort part of array from the start to the middle point.
  4. Recursively Merge Sort part of array above the middle point.
  5. 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

Disqus Comments