What is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm. It splits the array in half, recursively sorts each half, then merges the sorted halves back together. It guarantees O(n log n) performance in all cases.

The Basic Idea

Merge sort works by:

Why Merge Sort is Reliable

Merge sort is popular because:

1. Guaranteed performance: Always O(n log n)
2. Stable: Maintains relative order of equal elements
3. Predictable: Same performance regardless of input
4. Parallelizable: Can be easily parallelized

Visual Example

Watch merge sort in action:

Key Characteristics

• Time complexity: O(n log n) in all cases
• Space complexity: O(n) - needs extra array
• Stable: Yes - maintains order of equal elements
• Not in-place: Requires O(n) extra space

Real-World Use

Merge sort is used in:

• Standard library implementations
• External sorting (sorting large files)
• Database systems
• When stability is required
• When guaranteed performance is needed

What’s Next?

Now that you know what merge sort is, let’s see exactly how it works.