AI WisdomApply this in AI systems ↗

PyAnimate

Interactive Python Lab

AI Wisdom

Loading playground…

PyAnimate

Interactive Python Lab

AI Wisdom

Interactive Python Lab

Merge Sort

The playground auto-runs on load. Hit Run My Code to trace your own Python — every step animated live.

Explain·Line by line

Replay·Step by step

Challenge·Guided prompts

XP·...

Data Flow Pipeline

advanced Track

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

Explain

Line 1

merge_sort splits array recursively until single elements remain.

Why this approach?

The base case is len(arr) <= 1: a single element is always sorted. This stops the recursion. Without the base case, the function would recurse infinitely.

Structured Explanation

Overview

Merge Sort splits the array, sorts each half, then merges the sorted halves.

Analogy

Shuffling two sorted decks into one by always picking the smaller top card.

Step-by-step

Divide array into left and right halves until size 1.
Recursively sort each half.
Merge: walk both halves with pointers, take the smaller each step.
Copy merged result back.
Return the combined sorted array.

Visual

Recursion tree halves the list; merge step interleaves two sorted rows.

Common mistakes

Missing the base case (length ≤ 1).
Forgetting to append remaining tail elements during merge.
Allocating fresh buffers repeatedly instead of reusing.

Practice questions

Trace merge sort on [5,2,4,6,1,3] writing each merge output.
Explain why merge sort is stable and when stability matters.
Compute recursion tree height and extra memory needed.

Time

O(n log n)

Space

O(n) auxiliary for merge buffer

Complexity

Time

O(n log n)

Space

O(n)

Complexity Overview

O(1)

O(log n)time

O(n)space

O(n log n)time

O(n²)

n = 8range 1-20

AT N = 8

Complexity	Operations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Challenge

Change arr to [9, 3, 7, 1, 5, 2, 8]. How many recursive calls does merge sort make?

Hint

Each call splits into two — the total calls form a binary tree with log₂(n) levels. For n=7 that's about 3 levels.

Code Studio

Merge Sort

Monaco Ready

Python ready

lesson.pyline 1

Loading editor...

Output Console

0 lines

No output yet...

Real-World Applications

Sorting linked lists (merge sort is natural for them)

External sort: merging sorted files too large for RAM

Count inversions in an array

Stable sort used in Python's built-in sorted() (Timsort is based on it)

Loading playground…

Interactive Python Lab

Merge Sort

The playground auto-runs on load. Hit Run My Code to trace your own Python — every step animated live.

Explain·Line by line

Replay·Step by step

Challenge·Guided prompts

XP·...

Data Flow Pipeline

advanced Track

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

Explain

Line 1

merge_sort splits array recursively until single elements remain.

Why this approach?

The base case is len(arr) <= 1: a single element is always sorted. This stops the recursion. Without the base case, the function would recurse infinitely.

Structured Explanation

Overview

Merge Sort splits the array, sorts each half, then merges the sorted halves.

Analogy

Shuffling two sorted decks into one by always picking the smaller top card.

Step-by-step

Divide array into left and right halves until size 1.
Recursively sort each half.
Merge: walk both halves with pointers, take the smaller each step.
Copy merged result back.
Return the combined sorted array.

Visual

Recursion tree halves the list; merge step interleaves two sorted rows.

Common mistakes

Missing the base case (length ≤ 1).
Forgetting to append remaining tail elements during merge.
Allocating fresh buffers repeatedly instead of reusing.

Practice questions

Trace merge sort on [5,2,4,6,1,3] writing each merge output.
Explain why merge sort is stable and when stability matters.
Compute recursion tree height and extra memory needed.

Time

O(n log n)

Space

O(n) auxiliary for merge buffer

Complexity

Time

O(n log n)

Space

O(n)

Complexity Overview

O(1)

O(log n)time

O(n)space

O(n log n)time

O(n²)

n = 8range 1-20

AT N = 8

Complexity	Operations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Challenge

Change arr to [9, 3, 7, 1, 5, 2, 8]. How many recursive calls does merge sort make?

Hint

Each call splits into two — the total calls form a binary tree with log₂(n) levels. For n=7 that's about 3 levels.

Code Studio

Merge Sort

Monaco Ready

Python ready

lesson.pyline 1

Loading editor...

Output Console

0 lines

No output yet...

Real-World Applications

Sorting linked lists (merge sort is natural for them)

External sort: merging sorted files too large for RAM

Count inversions in an array

Stable sort used in Python's built-in sorted() (Timsort is based on it)