Python Merge Sort Algorithm Tutorial
Learn how to implement Merge Sort in Python. An interactive, step-by-step example of the Divide and Conquer sorting strategy.
How it Works
Merge Sort is a highly efficient sorting algorithm that utilizes a divide-and-conquer strategy. It breaks down an unsorted list into smaller sub-lists, sorts those sub-lists, and then merges them back together.
The algorithm recursively splits the array in half until it reaches single-element subarrays. Then, it merges the sorted sub-arrays by comparing elements from each side and placing them in sorted order. This ensures an optimal time complexity.
Regardless of whether the initial array is sorted, reversed, or completely random, Merge Sort executes in O(n log n) time. However, it requires O(n) extra space to hold the sub-lists during the merging phase.
Source Code
A standard recursive implementation of the Merge Sort algorithm in Python.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]Real-world Applications
- Sorting linked lists where node structure facilitates easy merging without copying
- External sorting routines for files that do not fit entirely in system RAM
- Stable sorting applications where matching keys must preserve their original order
Frequently Asked Questions
Is Merge Sort a stable sorting algorithm?
Yes, Merge Sort is stable. When comparing identical elements, the element from the left (original first) subarray is placed first, preserving their original relative positions.
Why does Python use Timsort instead of pure Merge Sort?
Python's built-in `sorted()` uses Timsort, which is a hybrid algorithm combining Merge Sort and Insertion Sort. It optimizes real-world data patterns by identifying already-sorted sub-segments, rendering it faster than pure Merge Sort.