Python Merge Sort Tutorial
last modified March 8, 2025
In this article, we explain the merge sort algorithm and demonstrate its use in Python.
An algorithm is a step-by-step procedure for solving a problem or performing a computation. Algorithms are fundamental to computer science and programming.
Sorting is the process of arranging data in a specific order, such as ascending or descending. Sorting is essential for efficient data retrieval and analysis.
Common Sorting Algorithms
Some common sorting algorithms include:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
Merge Sort Algorithm
Merge Sort is a divide-and-conquer algorithm. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves.
Merge Sort Example
Below is a Python implementation of the Merge Sort algorithm.
def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] merge_sort(left_half) merge_sort(right_half) i = j = k = 0 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1 def sort_ascending(arr): merge_sort(arr) return arr def sort_descending(arr): merge_sort(arr) return arr[::-1] # Example usage numbers = [38, 27, 43, 3, 9, 82, 10] words = ["apple", "banana", "cherry", "date", "elderberry"] print("Sorted numbers (ascending):", sort_ascending(numbers)) print("Sorted numbers (descending):", sort_descending(numbers)) print("Sorted words (ascending):", sort_ascending(words)) print("Sorted words (descending):", sort_descending(words))
The merge_sort
function sorts the array in ascending order. The sort_ascending
and sort_descending
functions use merge_sort
to sort the array in ascending and descending order, respectively.
$ ./merge_sort.py Sorted numbers (ascending): [3, 9, 10, 27, 38, 43, 82] Sorted numbers (descending): [82, 43, 38, 27, 10, 9, 3] Sorted words (ascending): ['apple', 'banana', 'cherry', 'date', 'elderberry'] Sorted words (descending): ['elderberry', 'date', 'cherry', 'banana', 'apple']
Comparing Merge Sort with Quick Sort
Merge Sort and Quick Sort are both efficient sorting algorithms. Merge Sort has a consistent time complexity of O(n log n), while Quick Sort has an average time complexity of O(n log n) but can degrade to O(n^2) in the worst case.
Below is a benchmark comparing the performance of Merge Sort and Quick Sort.
import time import random def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) def benchmark(sort_func, arr): start_time = time.time() sort_func(arr) end_time = time.time() return end_time - start_time # Generate a large list of random numbers random_numbers = [random.randint(0, 10000) for _ in range(10000)] # Benchmark Merge Sort merge_sort_time = benchmark(lambda arr: merge_sort(arr), random_numbers.copy()) # Benchmark Quick Sort quick_sort_time = benchmark(lambda arr: quick_sort(arr), random_numbers.copy()) print(f"Merge Sort Time: {merge_sort_time:.6f} seconds") print(f"Quick Sort Time: {quick_sort_time:.6f} seconds")
The benchmark compares the time taken by Merge Sort and Quick Sort to sort a large list of random numbers.
Source
In this article, we have explained and demonstrated the Merge Sort algorithm in Python.
Author
List all Python tutorials.