Time Complexity
Best: O(n log n)
Avg: O(n log n)
Worst: O(n log n)
Merge Sort is a stable, divide-and-conquer sorting algorithm. It divides the array into halves, recursively sorts each half, then merges the sorted halves.
How it works:
1. Divide the array into two halves
2. Recursively sort each half
3. Merge the two sorted halves into a single sorted array
4. The merge step compares elements from both halves and places them in order
Time Complexity:
Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Space Complexity: O(n) — requires temporary array
Properties:
- Stable sort
- Not in-place (requires O(n) extra space)
- Predictable performance (always O(n log n))
- Parallelizable
Merge Sort guarantees O(n log n) performance regardless of input. Ideal when stability is required or for sorting linked lists.
Related algorithms
Frequently asked questions
- What is Merge Sort?
- Merge Sort is a stable, divide-and-conquer sorting algorithm. It divides the array into halves, recursively sorts each half, then merges the sorted halves.
- What is the complexity of Merge Sort?
- Time (average): O(n log n) · Space: O(n)
- Who is this Merge Sort visualizer for?
- The Merge Sort visualization targets intermediate-level learners in the Sorting category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Merge Sort?
- In the same category (Sorting) you can explore: Bubble Sort, Selection Sort, Insertion Sort. Each has an interactive visualization.