Python Program for Merge Sort

---

• Merge Sort algorithm using a Divide and Conquer strategy and It divides input array in two halves.Merge sort is a recursive algorithm that continually divides a list into half.
• If the list is empty or an item, then it is sorted by definition. If there are more than one item in the list, then we split the list and recursively invoke a merge sort on both the parts.
• Once the two halves are sorted, the basic operation, which is called merge, is performed. merging is the process of taking two short layoff lists and combining them together in a single, sorted, new list.

---

def merge_Sort(arr_list):
    print("Splitting of elements ",arr_list)
    if len(arr_list)>1:
        middle = len(arr_list)//2
        left = arr_list[:middle]
        right = arr_list[middle:]

        merge_Sort(left)
        merge_Sort(right)

        i=0
        j=0
        k=0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr_list[k]=left[i]
                i=i+1
            else:
                arr_list[k]=right[j]
                j=j+1
            k=k+1

        while i < len(left):
            arr_list[k]=left[i]
            i=i+1
            k=k+1

        while j < len(right):
            arr_list[k]=right[j]
            j=j+1
            k=k+1
    print("Merging of elements ",arr_list)

arr_list = [91,22,43,97,17,81,14,25,120,200]
merge_Sort(arr_list)
print("Sorted elements are : ", arr_list)

Output:-

('Splitting of elements ', [91, 22, 43, 97, 17, 81, 14, 25, 120, 200])
('Splitting of elements ', [91, 22, 43, 97, 17])
('Splitting of elements ', [91, 22])
('Splitting of elements ', [91])
('Merging of elements ', [91])
('Splitting of elements ', [22])
('Merging of elements ', [22])
('Merging of elements ', [22, 91])
('Splitting of elements ', [43, 97, 17])
('Splitting of elements ', [43])
('Merging of elements ', [43])
('Splitting of elements ', [97, 17])
('Splitting of elements ', [97])
('Merging of elements ', [97])
('Splitting of elements ', [17])
('Merging of elements ', [17])
('Merging of elements ', [17, 97])
('Merging of elements ', [17, 43, 97])
('Merging of elements ', [17, 22, 43, 91, 97])
('Splitting of elements ', [81, 14, 25, 120, 200])
('Splitting of elements ', [81, 14])
('Splitting of elements ', [81])
('Merging of elements ', [81])
('Splitting of elements ', [14])
('Merging of elements ', [14])
('Merging of elements ', [14, 81])
('Splitting of elements ', [25, 120, 200])
('Splitting of elements ', [25])
('Merging of elements ', [25])
('Splitting of elements ', [120, 200])
('Splitting of elements ', [120])
('Merging of elements ', [120])
('Splitting of elements ', [200])
('Merging of elements ', [200])
('Merging of elements ', [120, 200])
('Merging of elements ', [25, 120, 200])
('Merging of elements ', [14, 25, 81, 120, 200])
('Merging of elements ', [14, 17, 22, 25, 43, 81, 91, 97, 120, 200])
('Sorted elements are : ', [14, 17, 22, 25, 43, 81, 91, 97, 120, 200])


 

---