Merge Sort

 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)

1.        If the list has zero or one item, it is already sorted.
      → Just return it.
2.        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.
3.        After both halves are sorted, combine them back together in the correct order using the merge steps.
4.        Return the final sorted list.

---

Merge (joining two sorted lists) — Plain English Steps

1.        Start with two lists that are already sorted.
2.        Create an empty list to store the result.
3.        Look at the first item in each list.
4.        Pick the smaller one and put it into the result list.
5.        Remove that item from its list.
6.        Repeat the comparison until one list becomes empty.
7.        When one list has no more items, add everything left from the other list to the result.
8.        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)