Merge Sort
Merge Sort:
- Break the list into halves until each piece has
one item.
- Sort the pieces (they are already sorted because
they are single items).
- Join pieces back together in sorted order.
Merge Sort
Algorithm (Plain English)
- If the list has zero or one item, it is
already sorted.
→ Just return it. - If the list has more than one item:
- Find the middle point of the list.
- Split the list into two smaller lists:
left half and right half. - Sort the left half by repeating the merge
sort steps.
- Sort the right half by repeating the merge
sort steps.
- After both halves are sorted, combine them back
together in the correct order using the merge steps.
- Return the final sorted list.
Merge (joining
two sorted lists) — Plain English Steps
- Start with two lists that are already sorted.
- Create an empty list to store the result.
- Look at the first item in each list.
- Pick the smaller one and put it into the
result list.
- Remove that item from its list.
- Repeat the comparison until one list becomes empty.
- When one list has no more items, add everything
left from the other list to the result.
- The result is now a fully sorted list.
# Merge sort
# Function to merge sorted lists
def merge(a, b):
c = []
while (len(a) != 0 and len(b) != 0):
if a[0] < b[0]:
c.append(a[0])
a.remove(a[0])
else:
c.append(b[0])
b.remove(b[0])
if(len(a) == 0):
c = c + b
else:
c += a
return c
# Function - create sublists
def mergesort(L1):
if len(L1) == 0 or len(L1) == 1:
return L1
else:
middle = len(L1)//2
a = mergesort(L1[:middle])
b = mergesort(L1[middle:])
return merge(a,b)
# Read elements and create list
Original_List = eval(input("Enter list of elements : "))
Sorted_list = mergesort(Original_List)
print("Original list :", Original_List)
print("Sorted List :", Sorted_list)
