# Merge Sort Python Program-Implementation In 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.

```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

•
•
•
•
•
•
•
•

### You May Also Like

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