Merge Sort
Problem statement
Write a python program to sort the given list using mergesort algorithm
Examples:
Input:[5,8,2]
Output:[2,5,8]
Input:[6,2,8,4,3,7,5,1]
Output:[1,2,3,4,5,6,7,8]
Input=[6,-2,8,4,-3,7,-5,1]
Output=[-5,-3,-2,1,4,6,7,8]
Input=[6,-2,"8.8",4.4,-3,7.5,-5,1]
Output="Invalid input"
Input=23
Output="Invalid input"How it works
Before sorting: [6, 5, 3, 1, 8, 7, 2, 3]
[6, 5, 3, 1, 8, 7, 2, 3]
divide left: [6, 5, 3, 1]
divide left: [6, 5]
divide left: [6]
divide right: [5]
merging: [6] [5] merged: [5, 6]
divide right: [3, 1]
divide left: [3]
divide right: [1]
merging: [3] [1] merged: [1, 3]
merging: [5, 6] [1, 3] merged: [1, 3, 5, 6]
divide right: [8, 7, 2, 3]
divide left: [8, 7]
divide left: [8]
divide right: [7]
merging: [8] [7] merged: [7, 8]
divide right: [2, 3]
divide left: [2]
divide right: [3]
merging: [2] [3] merged: [2, 3]
merging: [7, 8] [2, 3] merged: [2, 3, 7, 8]
merging: [1, 3, 5, 6] [2, 3, 7, 8] merged: [1, 2, 3, 3, 5, 6, 7, 8]
After sorting: [1, 2, 3, 3, 5, 6, 7, 8]Related material
Animation - https://visualgo.net/en/sorting?slide=10 slides - http://bit.ly/KG_mergesort
Pseudo code
merge_sort(num)
return divide(num)
divide(num)
if num is empty or len(num) is 1:
return num
mid = len(num)/2
left = divide(num[:mid])
right = divide(num[mid:])
merge(left,right)
merge(left,right)
merged_list = [ ]
while left and right are not empty:
if left[0] < right[0]:
Pop left[0] and add it to merged_list
else:
Pop right[0] and add it to merged_list
Append remaining left and right to merged_listSolution key
def mergesort(numbers):
# check for the empty list or the list with single element
if not numbers or len(numbers) == 1:
return numbers
# recursive splitting (Divide)
else:
mid = len(numbers)//2
left = mergesort(numbers[:mid])
right = mergesort(numbers[mid:])
return merge(left, right)
def merge(left, right):
# left and right are the sorted lists to be merged
# The merged list after sorting
merged = []
# Loop till left or right becomes empty
while left and right:
# remove the minimum of left[0] and right[0]
# and add it to the merged list
if left[0] < right[0]:
merged += [left.pop(0)]
else:
merged += [right.pop(0)]
# add the remaining elements of left, if any
merged += left
# add the remaining elements of right, if any
merged += right
return mergedPre-Lab Questions
How do you get the number of elements in the list
Merge two lists [2,4,3] and [7,5,6]
Consider
leftandrightlists of size 1. Merge them in a sorted order.
Example:
left = [12] right = [3]
merged = [3,12]Now consider the two sorted lists of unspecified size. Merge them in a sorted order.
Example:
left = [12,45] right = [3,17]
merged = [3,12,17,45]4b. Merge two sorted lists [2,6,7] and [3,5,8] in the sorted order
Divide the list
numintoleftandrighthalves.
Example:
num = [6,2,8,4,3,7,5,1]
left = [6,2,8,4] right = [3,7,5,1]Recursively divide, till the partition size is 1
Example:
num = [12,3,45,17,15]
left = [12,3]
left = [12]
right = [3]
right = [17, 15]
left = [17]
right = [15]What are the first two elements to be merged from the input list [6,2,8,4,3,7,5,1] in the mergesort
Validate whether given input is of
listtype.Validate whether all the elements in the input are of
inttype.Validate whether given list is empty
Post-Lab Questions
Modify the program to validate whether given input is a valid list.
Modify the code to sort the list of string elements.
example:
input=['python','c','c++','java']
expected output=['c','c++','python','java']Bonus
What is the worst case complexity for merge sort algorithm?
Interview Grade
Why quicksort is better than mergesort?
Is there a way to implement a hybrid sort (which uses MergeSort and InsertionSort)? What is the algorithm for this? Clue: Dynamic Task Parallelism https://msdn.microsoft.com/en-us/library/ff963551.aspx
CyberDojo session
CD extrenal Link : http://cyberdojo1.kgfsl.com/kata/edit/B006BC6DA0?avatar=bee
CD local Link : http://10.100.8.8/kata/edit/B006BC6DA0?avatar=bee
Test cases
from mergesort import mergesort
import unittest
import random
class Test_mergesort(unittest.TestCase):
def test_one_number(self):
print("test 1")
expected=[5]
actual=mergesort([5])
self.assertEqual(expected,actual)
def test_two_numbers(self):
print("test 2")
expected=[2,5]
actual=mergesort([5,2])
self.assertEqual(expected,actual)
def test_three_numbers_ordered_right(self):
print("test 3")
expected=[2,5,8]
input=[5,2,8]
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_three_numbers_unordered(self):
print("test 4")
expected=[2,5,8]
actual=mergesort([5,8,2])
self.assertEqual(expected,actual)
def test_bigger_list(self):
print("test 5")
input=[6,2,8,4,3,7,5,1]
expected=[1,2,3,4,5,6,7,8]
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_empty(self):
print("test 6")
input=[]
expected=[]
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_negative_numbers(self):
print("test 7")
input=[6,-2,8,4,-3,7,-5,1]
expected=[-5,-3,-2,1,4,6,7,8]
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_float(self):
print("test 8")
input=[6,-2,8.8,4.4,-3,7.5,-5,1]
expected=[-5,-3,-2,1,4.4,6,7.5,8.8]
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_non_number(self):
print("test 9")
input=[6,-2,"8.8",4.4,-3,7.5,-5,1]
expected="Invalid input"
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_non_list(self):
print("test 10")
input=23
expected="Invalid input"
actual=mergesort(input)
self.assertEqual(expected,actual)
def test_random(self):
print("Random test input")
input=[random.uniform(1,10) for _ in range(10)]
expected=sorted(input)
actual=mergesort(input)
self.assertEqual(expected,actual)
if __name__ == '__main__':
unittest.main()Answer key for validating the input
def mergesort(numbers):
# Top level function to validate the input once
if not is_valid(numbers):
return "Invalid input"
# Original `mergedsort` function is renamed as `split`
return split(numbers)
def is_valid(numbers):
if(type(numbers) != list):
return False
for elem in numbers:
if not isinstance(elem, int) and not isinstance(elem, float):
return False
return TrueLast updated