Merge Sort Python Program-Implementation In Python

mergesort python

Merge sort is the most efficient algorithm. It is working on the principle of divide and conquer .

Merge sort have a Best case time complexity Ω(n log(n)) and worst case O(n log(n)).

It is a top down recursive sorting algorithm.

merge sort algorithm
merge sort algorithm in c
def merge_lists(left_sublist,right_sublist):
	i,j = 0,0
	result = []
	#iterate through both left and right sublist
	while i<len(left_sublist) and j<len(right_sublist):
		#if left value is lower than right then append it to the result
		if left_sublist[i] <= right_sublist[j]:
			result.append(left_sublist[i])
			i += 1
		else:
			#if right value is lower than left then append it to the result
			result.append(right_sublist[j])
			j += 1
	#concatenate the rest of the left and right sublists
	result += left_sublist[i:]
	result += right_sublist[j:]
	#return the result
	return result

def merge_sort(input_list):
	#if list contains only 1 element return it
	if len(input_list) <= 1:
		return input_list
	else:
		#split the lists into two sublists and recursively split sublists
		midpoint = int(len(input_list)/2)
		left_sublist = merge_sort(input_list[:midpoint])
		right_sublist = merge_sort(input_list[midpoint:])
		#return the merged list using the merge_list function above
		return merge_lists(left_sublist,right_sublist)


#test run
numberlist = [3,1,5,3,2,5,8,2,9,6,12,53,75,22,83,123,12123]
print merge_sort(numberlist)

credits: femmerling

Similar Posts:

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

You May Also Like

About the Author: shakirck

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.