Try it yourself

Run this code directly in your browser. Click "Open in full editor" to experiment further.

Loading...

Click Run to see output

Or press Ctrl + Enter

How it works

Merge Sort is an amazingly smart sorting algorithm that uses a legendary strategy called Divide and Conquer!

How It Works

Imagine you have a giant, messy stack of 100 test papers to sort alphabetically. Sorting all 100 at once is totally overwhelming!

1. Divide: What if you just rip the stack in half? Now you have two stacks of 50. Still too big? Keep ripping them in half until you just have 100 individual papers! (Because a stack of exactly 1 paper is technically already sorted!)

2. Conquer (Merge): Now, look at two individual papers. Put them in order. Boom! You have a sorted stack of 2 papers! Take another sorted stack of 2, and merge them perfectly into a sorted stack of 4!

3. Keep stitching these perfectly sorted mini-stacks together until the whole giant stack is perfectly sorted.

Why is it so awesome?

Guaranteed Fast Performance: No matter how messy the array is (even if it's completely completely backwards), Merge Sort will always take exactly O(n log n) time. It never slows down unexpectedly like other algorithms!

Stable Sort: If you have two identical numbers (like two 5s) in your list, the one that was originally first will stay first! It respects the original order.

Time and Space Complexity

Time Complexity: O(n log n) — Consistently blazing fast!

Space Complexity: O(n) — Since we have to create those new mini-lists during our merging process, we need some extra memory space to hold them while we work.

When to Use

When guaranteed, unwavering fast performance is needed.

When you are sorting massive datasets that are too large to fit in memory (Merge sort is great at "External sorting"!)

Related examples

Algorithms

Merge Sort in Python