This is a Python program to implement merge sort.
The program sorts a list by merge sort.
1. Create a function merge_sort that takes a list and two variables start and end as arguments.
2. The function merge_sort will sort the list from indexes start to end – 1 inclusive.
3. If end – start is not greater than 1, then return.
4. Otherwise, set mid equal to the floor of (start + end)/2.
5. Call merge_sort with the same list and with start = start and end = mid as arguments.
6. Call merge_sort with the same list and with start = mid and end = end as arguments.
7. Call the function merge_list, passing the list and the variables start, mid and end as arguments.
8. The function merge_list takes a list and three numbers, start, mid and end as arguments and assuming the list is sorted from indexes start to mid – 1 and from mid to end – 1, merges them to create a new sorted list from indexes start to end – 1.
Here is the source code of a Python program to implement merge sort. The program output is shown below.
def merge_sort(alist, start, end): '''Sorts the list from indexes start to end - 1 inclusive.''' if end - start > 1: mid = (start + end)//2 merge_sort(alist, start, mid) merge_sort(alist, mid, end) merge_list(alist, start, mid, end) def merge_list(alist, start, mid, end): left = alist[start:mid] right = alist[mid:end] k = start i = 0 j = 0 while (start + i < mid and mid + j < end): if (left[i] <= right[j]): alist[k] = left[i] i = i + 1 else: alist[k] = right[j] j = j + 1 k = k + 1 if start + i < mid: while k < end: alist[k] = left[i] i = i + 1 k = k + 1 else: while k < end: alist[k] = right[j] j = j + 1 k = k + 1 alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist] merge_sort(alist, 0, len(alist)) print('Sorted list: ', end='') print(alist)
1. The user is prompted to enter a list of numbers.
2. The list is passed to the merge_sort function.
3. The sorted list is displayed.
Case 1: Enter the list of numbers: 3 1 5 8 2 5 1 3 Sorted list: [1, 1, 2, 3, 3, 5, 5, 8] Case 2: Enter the list of numbers: 5 3 2 1 0 Sorted list: [0, 1, 2, 3, 5] Case 3: Enter the list of numbers: 1 Sorted list: [1]
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.
- Get Free Certificate of Merit in Python Programming
- Participate in Python Programming Certification Contest
- Become a Top Ranker in Python Programming
- Take Python Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Information Technology Books
- Buy Python Books
- Apply for Python Internship
- Apply for Programming Internship
- Practice Programming MCQs