learningto/pass

Sorting

EasyAlgorithms

Sorting underpins many algorithmic techniques. Beyond knowing the standard algorithms, interviewers want you to recognize when counting sort beats comparison sort and when merge sort is preferable to quicksort.

AVG TIME
O(n log n)
SPACE
O(log n)
BEST
O(n log n)
WORST
O(n^2)

Step-by-Step Walkthrough

step-by-step walkthrough

Merge Sort

1 / 6
algorithm.py
1def merge_sort(arr):
2 if len(arr) <= 1:
3 return arr
4
5 mid = len(arr) // 2
6 left = merge_sort(arr[:mid])
7 right = merge_sort(arr[mid:])
8 return merge(left, right)
9
10def merge(left, right):
11 result = []
12 i = j = 0
13 while i < len(left) and j < len(right):
14 if left[i] <= right[j]:
15 result.append(left[i]); i += 1
16 else:
17 result.append(right[j]); j += 1
18 result.extend(left[i:])
19 result.extend(right[j:])
20 return result
visualization
input
8
0
3
1
1
2
5
3
2
4
7
5
variable inspectorO(n log n)
arr=[8, 3, 1, 5, 2, 7]
The Input Array
We want to sort [8, 3, 1, 5, 2, 7]. Merge sort follows "divide and conquer": split the problem into smaller pieces, solve each piece, combine the results. We'll split until each piece has 1 element (which is already sorted by definition).
speedmed
← →space

In Python

Concept to Code- 1 structure for this topic
declare
nums = [1, 2, 3]
common ops
nums.append(x)
O(1)
nums.pop()
O(1)
nums[i]
O(1)
nums.insert(i, x)
O(n)
x in nums
O(n)
nums.sort()
O(n log n)
len(nums)
O(1)
say in interview
"I'll use an array to store the elements"
Python lists ARE dynamic arrays (like ArrayList in Java), NOT linked lists. Access by index is O(1).

Math You Need For This

Merge sort: split a deck of 16 cards into halves, then quarters, then singles (log₂(16)=4 splits). Merge the singles into sorted pairs - 8 merges. Merge pairs into fours - 4 merges. Each round does n total work across 4 rounds = 4n = n log n.

Required concepts
Key math ideas
1 / 4

Logarithms - "how many times can you cut in half?"

log₂(n) answers this question: if you start with n things and keep cutting the group in half, how many cuts until you reach 1? For 1,024 items that is only 10 cuts. For a million items it is about 20. The number barely grows even as n explodes.

Remaining1024 items (log₂(1024) = 10)
Clicks so far: 0

Think of it this way: A phone book with 1,024 names. Flip to the middle - is your name before or after? Flip to the middle of the surviving half. Repeat. You find any name in at most 10 flips, not 1,024.

For algorithms: Any algorithm that cuts its remaining work in half each step runs in O(log n). Binary search, balanced tree lookups, and heap operations all work this way.

Interactive 3D Visualization

Sorting Algorithms
Bubble: O(n²)Quick: O(n log n)*Space: O(1)-O(n)
Drag to orbit - Scroll to zoom

Brute Force vs Optimized

Interview Strategy - Sort an Array

Start brute force, explain it, THEN optimize. "I can see a straightforward approach. Let me start there, then we can optimize."

Brute Force
Bubble Sort
TimeO(n^2)
SpaceO(1)

"Compare adjacent elements, swap if out of order. Repeat until sorted."

Pros
  • +Extremely simple to code
  • +In-place - no extra memory
  • +Good for nearly-sorted data
Cons
  • -Quadratic time - unusable for large inputs
  • -Never use in an interview unless asked
Optimized
Merge Sort
TimeO(n log n)
SpaceO(n)

"Divide array in half recursively, merge sorted halves back together."

Pros
  • +Guaranteed O(n log n) - no worst case
  • +Stable sort
  • +Divide-and-conquer pattern
Cons
  • -O(n) extra space for merging
  • -More complex to implement
The Tradeoff

Trading O(n) space to go from O(n^2) to O(n log n). For n=10,000: bubble sort does 100,000,000 comparisons. Merge sort does 130,000.

For n=10,000
Brute Force100,000,000 ops
Optimized130,000 ops
Say This

Say: "O(n log n) is the theoretical lower bound for comparison-based sorting. Merge sort guarantees this. Quick sort achieves it on average with better constants."

Watch It Run

Merge Sort
Divide-and-conquer: split until trivial, merge back in sorted order.
SPEED
1 / 9
Your data
algorithm.py
1>def merge_sort(arr):
2  if len(arr) <= 1:
3  return arr
4  mid = len(arr) // 2
5  left = merge_sort(arr[:mid])
6  right = merge_sort(arr[mid:])
7  return merge(left, right)
8 
9 def merge(left, right):
10  result = []
11  i = j = 0
12  while i < len(left) and j < len(right):
13  if left[i] <= right[j]:
14  resultappend(left[i])
15  i += 1
16  else:
17  resultappend(right[j])
18  j += 1
19  resultextend(left[i:])
20  resultextend(right[j:])
21  return result
array visualization
38[0]
27[1]
43[2]
3[3]
0
1
2
3
i

Starting merge_sort on [38, 27, 43, 3]. This is divide-and-conquer: split the problem in half recursively until trivial (1 element), then merge sorted halves back together.

VariablesStep 1 of 10 (full array)
arr=[3827433]
Spaceplay/pause← →step+ -speed

Python Implementation

example.py
Loading...
Now try it yourself
1 challenge with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Sorting into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Binary Search
Sorting
Next: Binary Search