Merge Sort in Python
Merge sort splits a list into smaller halves, sorts each half recursively, and merges the sorted results.
What is Merge Sort?
Merge sort splits a list into smaller halves, sorts each half recursively, and merges the sorted results.
Implement recursive merge sort in Python.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Merge Sort in Python visualizer
O(n log n)Use Play or Step to follow each comparison and data movement.
Example code
main.py
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))Expected output
[3, 9, 10, 27, 38, 43, 82]How it works
The recursion reaches lists of length one. Merging then rebuilds sorted lists from the bottom up. Time complexity is O(n log n).
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.