Python Tutorial

# Python Program for Merge Sort

## What is merge sort ?

Merge sort is a divide-and-conquer algorithm, here breaking down a list into multiple sub lists till each sub list consists of a single element and then merging all sub lists in order to get a sorted list.

## Merge Sort Algorithm

• Divide the unsorted list into multiple sub lists using mid index ( ( start index + end index) /2) until each sub list contains single element.
• Take two adjacent pairs of sub list and merge them as list of 2 elements.
• Repeat step 2 process till merging single sorted list of all elements.

## Merge Sorting Time complexity

Number of elements in the list is N, N is divided into a max of log N sub lists, and merging all sub lists into a single list takes O(N) time, Worst case run time O(N Log N).

## Merge Sort Python Program

```#!/usr/bin/python

def merge_list(list_vals,  start_index, mid_index, end_index):
# Starting position of both parts
p = start_index;
q = mid_index + 1;

sorted_list_vals= [];

for i in range(start_index, end_index+1):
# Checks whether 1st part is end or not.
if (p > mid_index):
sorted_list_vals.append(list_vals[q]);
q += 1;

# Checks whether 2nd part is end or not.
elif (q > end_index):
sorted_list_vals.append(list_vals[p]);
p += 1;

# Checks which part has samller element.
elif (list_vals[p] < list_vals[q]):
sorted_list_vals.append(list_vals[p]);
p += 1;

else:
sorted_list_vals.append(list_vals[q]);
q += 1;

for p in range(0, len(sorted_list_vals)):
list_vals[start_index] = sorted_list_vals[p];
start_index += 1;

def merge_sort(list_vals, start_index, end_index):
if (start_index < end_index):
# finding mid index
mid_index = (start_index + end_index ) / 2;
# sorting 1st part of the array.
merge_sort(list_vals, start_index, mid_index);
# sorting 2nd part of the array.
merge_sort(list_vals, mid_index+1, end_index);
# merge the both parts, comparing elements
merge_list(list_vals, start_index, mid_index, end_index);

if __name__ == "__main__":
list_vals = [30, 10, 20, 70, 60, 80, 50, 40];
print("Collection before sorting: %s" % str(list_vals));
merge_sort(list_vals, 0, len(list_vals)-1);
print("Sorted list elements: %s" % str(list_vals));
```
Output:
```\$ python  merge_sort.py
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]
```

Python Tutorial