← Back to Home
Merge Sort
An efficient, stable, comparison-based sorting algorithm using the divide and conquer paradigm.
Visualization
Step 1 / 10
Speed:
Details
Analogy
Think of two librarians, each with a stack of books sorted alphabetically. To create one large, sorted stack, they compare the top book of each stack, take the one that comes first, and place it on a new pile. They repeat this until all books are merged into the single new, sorted pile.
Purpose
To sort an array by dividing it into two halves, recursively sorting them, and then merging the sorted halves.
Use Cases
Excellent for situations where stability is important (i.e., equal elements maintain their original order). Used in external sorting and parallel computing.
Algorithm Steps
Line 1
1
function mergeSort(arr, left, right):
2
if left < right:
3
mid = (left + right) / 2
4
mergeSort(arr, left, mid)
5
mergeSort(arr, mid+1, right)
6
merge(arr, left, mid, right)
7
8
function merge(arr, left, mid, right):
9
create temp arrays L and R
10
copy data to L and R
11
merge L and R back into arr
Current
Executed
Pending
Explanation
What's Happening?
Step 1/10
Initial array. The algorithm will recursively divide it.
Updates with each step • Clickfor full view
Code Implementation
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr