Python Merge Sort Algorithm: Explained with Examples, code and Video
Merge sort is the first divide and conquer algorithm that we explain in this series on algorithms that sort lists and arrays.
We start with the same example used in all the articles on algorithms, explaining the logic of how the merge sort works. This is followed by the merge sort in python code.
Other interesting details follow the tutorial video. In fact the explanation of the merge sort is available in two video formats, the short video and the normal length video (MergeSort | Easy | Algorithms | Simple Python Tutorials), both available on YouTube.
Sorting algorithms work by rearranging elements based on specific criteria, such as numerical value or alphabetical order. Different algorithms employ distinct strategies, including simple algorithms like bubble sort and selection sort, and more advanced like merge and quicksort.
Understanding the Merge Sort
Merge sort follows a simple approach utilizing the concept of divide and conquer and a recursive algorithm to sort a list of elements.
- Divide: The algorithm divides the input list into smaller sub lists until each sub list contains only one element. This process uses a recursive approach until no further division is possible.
- Conquer: Next, the algorithm begins merging the sub lists in pairs. It compares the elements in each pair and arranges them in the correct order, creating sorted sub lists.
- Merge: The sorted sub lists are merged again in pairs, with the elements compared and rearranged to create larger sorted sub lists. This process continues until the two sorted parts are merged into a single sorted list or sorted array.
Merge Sort Example
We will use this simple example of a python list of numbers to show examples of the merge sort algorithm.
The merge sort is a divide and conquer algorithm so it starts with the dividing each half.
As each half is also divided we continue to split the sub arrays into lists half the size of the previous stage.
This continues until we have subarrays, where the number of elements is one in each of the sublists.
Once we complete the divide process then it is time for the conquer part, or in this case, the merging.
In the first example, the digits 1 and 8 are already in the correct order.
In the first half of the list the numbers are merged into the correct order of 1,7 and 8.
In the other half we merge and order the final quarter of 2 and 3.
The second half is then merged into the correct order of 2, 3 and 4.
As we have two sorted halves, it is easy to then merge the two into the ordered list.
Video Tutorial
Implementing the Merge Sort in a Python Program
The merge sort algorithm in python has three main parts, the first is the divide part which is splitting the list into sub lists of half the size, until we have the single item sub parts.
def merge_sort(arr):
if len(arr) > 1:
left_arr = arr[:len(arr)//2]
right_arr = arr[len(arr)//2:]
#recursion
merge_sort(left_arr)
merge_sort(right_arr)We have the conquer and merge part which compares the numbers and puts them into order.
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1We also have the code that adds the end of either list if it is longer than the other list. This is more of a implementation part of the code rather than a logical part of the algorithm.
while i < len(left_arr):
arr[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1To complete the code we call the function. Here is the final and complete code of the merge sort algorithm in python.
def merge_sort(arr):
if len(arr) > 1:
left_arr = arr[:len(arr)//2]
right_arr = arr[len(arr)//2:]
#recursion
merge_sort(left_arr)
merge_sort(right_arr)
i = 0
j = 0
k = 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
arr[k] = left_arr[i]
i += 1
else:
arr[k] = right_arr[j]
j += 1
k += 1
while i < len(left_arr):
arr[k] = left_arr[i]
i += 1
k += 1
while j < len(right_arr):
arr[k] = right_arr[j]
j += 1
k += 1
return arr
arr = [7,1,8,4,3,2]
print("before ",arr)
print()
arr = merge_sort(arr)
print("sorted ",arr)
Complexity of Merge Sort vs Other Algorithms
When comparing merge sort with other algorithms used for sorting, several factors come into play, such as space and time complexity, space , stability, and adaptability to different scenarios. Let’s briefly compare merge sort with other approaches:
- Merge Sort vs. Quick Sort:
- Time : Both merge sort and quick sort have an average time complexity of O(n log n). However, quick sort can have a worst-case time complexity of O(n^2) in certain scenarios.
- Space : Merge sort has a space complexity of O(n) since it requires additional space to store the temporary sub lists during the merge phase. Quick sort typically has a space complexity of O(log n).
- Stability: Merge sort is stable, preserving the relative order of equal elements during the sorting process, while quick sort is not inherently stable.
- Merge Sort vs. Insertion Sort:
- Time : Both merge sort and insertion sort have an average time complexity of O(n log n) for comparison-based operations. However, insertion sort performs well on nearly sorted or small input sizes.
- Space : Merge sort has a higher space complexity of O(n) due to the additional space required for merging. Insertion sort operates in-place, with a space complexity of O(1).
- Adaptability: Insertion sort is well-suited for small or partially sorted datasets, while merge sort is more efficient for larger or unsorted datasets.
Merge Sort Questions and Answers
What is the merge sort algorithm?
The merge sort algorithm is a sorting technique that follows the divide and conquer paradigm. It recursively divides the input list into smaller sub lists, sorts them individually, and then merges them back together to obtain the final sorted list.
Why is merge sort considered efficient?
Merge sort has a time complexity of O(n log n), making it highly efficient for large datasets. It consistently performs well regardless of the initial order of elements, making it suitable for various sorting scenarios.
How do I implement merge sort in Python?
To implement merge sort in Python, you can follow these steps: (1) Divide the list into two halves, (2) Recursively apply merge sort on each half, (3) Merge these to obtain the final sorted list. The article provides a detailed code example to help you understand the implementation.
Can you provide a visual demonstration of merge sort?
Absolutely! In the accompanying video tutorial, we walk you through a step-by-step visualization of the merge sort algorithm in action. You’ll see how the elements are divided, sorted, and merged back together to achieve the desired order.
