About Merge Sort
Merge Sort is an efficient, general-purpose, comparison-based sorting algorithm. It uses a divide-and-conquer approach to sort elements by recursively dividing the array into smaller subarrays, sorting them, and then merging them back together.
Core Concepts
- Divide and Conquer: Breaks problem into smaller subproblems
- Recursive: Calls itself on smaller portions of the data
- Stable: Maintains relative order of equal elements
- Time Complexity: O(n log n) in all cases (best, average, and worst)
- Space Complexity: O(n) additional space required
- Best for: Large datasets where consistent performance is needed
The merge sort algorithm divides the array into two halves, recursively sorts them, and then merges the two sorted halves. The merge operation is the key process that combines two sorted arrays into a single sorted array.
Visualization
depth 0
1
2
3
4+