Python Pseudocode Writing Practice Problems & Exercises
Practice: Pseudocode Writing
← Back to lessonEasy
Translate the following pseudocode into a working Python function. Do not use the built-in max() function.
FUNCTION find_max(numbers)
SET max_val TO numbers[0]
FOR EACH item IN numbers (starting from index 1)
IF item > max_val THEN
SET max_val TO item
END IF
END FOR
RETURN max_val
END FUNCTION
Solution
def find_max(numbers):
# SET max_val TO numbers[0]
max_val = numbers[0]
# FOR EACH item IN numbers (starting from index 1)
for item in numbers[1:]:
# IF item > max_val THEN SET max_val TO item
if item > max_val:
max_val = item
# RETURN max_val
return max_val
print(find_max([3, 7, 2, 9, 4])) # 9
print(find_max([-5, -1, -8])) # -1
print(find_max([42])) # 42Mapping: Every pseudocode line maps 1-to-1 to a Python line. SET x TO y becomes x = y. FOR EACH ... IN becomes a for loop. IF ... THEN becomes if:. This is why pseudocode is powerful — when the design is clear, the translation is mechanical.
def find_max(numbers):
# Translate the pseudocode above into Python
pass
print(find_max([3, 7, 2, 9, 4])) # 9
print(find_max([-5, -1, -8])) # -1
print(find_max([42])) # 42Expected Output
9\n-1\n42Hints
Hint 1: The pseudocode sets max_val to the first element, then loops through the rest comparing each one.
Hint 2: In Python, you can iterate with `for item in numbers[1:]` to skip the first element you already assigned.
Your task: First write pseudocode for reversing a string (without using Python slicing Pseudocode: Python implementation: Key takeaway: Writing the pseudocode first made it obvious that we need a backward loop and an accumulator. The Python translation was straightforward once the logic was designed.[::-1] or reversed()), then implement it. Your pseudocode should handle the algorithm yourself, character by character.Solution
def reverse_string(text):
# SET result TO empty string
result = ""
# SET index TO length of text - 1
index = len(text) - 1
# WHILE index >= 0
while index >= 0:
# APPEND text[index] TO result
result += text[index]
# DECREMENT index BY 1
index -= 1
# RETURN result
return result
print(reverse_string("hello")) # olleh
print(reverse_string("Python")) # nohtyP
print(reverse_string("a")) # a
def reverse_string(text):
# Step 1: Write your pseudocode as comments
# Step 2: Implement each line
pass
print(reverse_string("hello")) # olleh
print(reverse_string("Python")) # nohtyP
print(reverse_string("a")) # aExpected Output
olleh\nnohtyP\naHints
Hint 1: Think about building a new string by walking through the original backwards — or by appending characters in reverse order.
Hint 2: One approach: start with an empty result string, loop from the last index down to 0, and concatenate each character.
Translate the following pseudocode into Python.
FUNCTION count_vowels(text)
SET vowels TO "aeiou"
SET count TO 0
FOR EACH character IN text
SET lower_char TO lowercase of character
IF lower_char IS IN vowels THEN
INCREMENT count BY 1
END IF
END FOR
RETURN count
END FUNCTION
Solution
def count_vowels(text):
# SET vowels TO "aeiou"
vowels = "aeiou"
# SET count TO 0
count = 0
# FOR EACH character IN text
for character in text:
# SET lower_char TO lowercase of character
lower_char = character.lower()
# IF lower_char IS IN vowels
if lower_char in vowels:
# INCREMENT count BY 1
count += 1
# RETURN count
return count
print(count_vowels("Hello World")) # 3
print(count_vowels("AEIOU aeiou")) # 10
print(count_vowels("rhythm")) # 0Mapping notes: SET x TO y becomes assignment. IS IN becomes Python's in operator. INCREMENT count BY 1 becomes count += 1. The pseudocode made the case-insensitive logic explicit upfront — converting to lowercase before comparing.
def count_vowels(text):
# Translate the pseudocode above into Python
pass
print(count_vowels("Hello World")) # 3
print(count_vowels("AEIOU aeiou")) # 10
print(count_vowels("rhythm")) # 0Expected Output
3\n10\n0Hints
Hint 1: The pseudocode converts each character to lowercase before checking — in Python use `.lower()` on the character.
Hint 2: The vowel set in Python can be a string "aeiou" and you check membership with `in`.
Medium
Write pseudocode for binary search on a sorted list, then translate it to Python. Your function should return the index of the target or -1 if not found.
Think through: What are the boundaries? When do you stop? How do you narrow the search space? Pseudocode: Python implementation: Why pseudocode helps here: Binary search has subtle off-by-one bugs. Writing the pseudocode first forces you to think through the loop invariant (Solution
def binary_search(sorted_list, target):
# SET low TO 0
low = 0
# SET high TO length of sorted_list - 1
high = len(sorted_list) - 1
# WHILE low <= high
while low <= high:
# SET mid TO (low + high) // 2
mid = (low + high) // 2
# IF sorted_list[mid] EQUALS target
if sorted_list[mid] == target:
return mid
# ELSE IF sorted_list[mid] < target
elif sorted_list[mid] < target:
low = mid + 1
# ELSE (target is in left half)
else:
high = mid - 1
# RETURN -1 (target not found)
return -1
print(binary_search([1, 3, 5, 7, 9, 11, 13], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11, 13], 4)) # -1
print(binary_search([2, 4, 6, 8, 10], 10)) # 4
print(binary_search([], 5)) # -1low <= high), the midpoint calculation, and which boundary to update. The three branches (found, go right, go left) become obvious in pseudocode before you worry about Python syntax.
def binary_search(sorted_list, target):
# Step 1: Write your pseudocode as comments
# Step 2: Implement each line
# Return the index of target, or -1 if not found
pass
print(binary_search([1, 3, 5, 7, 9, 11, 13], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11, 13], 4)) # -1
print(binary_search([2, 4, 6, 8, 10], 10)) # 4
print(binary_search([], 5)) # -1Expected Output
3\n-1\n4\n-1Hints
Hint 1: Binary search maintains two pointers (low, high) and repeatedly checks the middle element — if the target is smaller, move high; if larger, move low.
Hint 2: Be careful with the midpoint calculation: use `(low + high) // 2`. The loop continues while low <= high.
Design pseudocode for a retry mechanism with exponential backoff — a pattern used in every production system that calls external services. Then implement it in Python.
Requirements:
- Call
operation()up tomax_retriestimes - On failure, wait
base_delay * 2^attemptseconds (with small random jitter) - On success, return the result immediately
- If all retries fail, raise the last exception
Solution
Pseudocode:
FUNCTION retry_with_backoff(operation, max_retries, base_delay)
FOR attempt FROM 0 TO max_retries - 1
TRY
SET result TO operation()
RETURN result (success — exit immediately)
CATCH exception AS error
IF attempt EQUALS max_retries - 1 THEN
RAISE error (last attempt — give up)
END IF
SET delay TO base_delay * (2 ^ attempt)
SET jitter TO random value between 0 and delay * 0.1
WAIT FOR delay + jitter seconds
END TRY
END FOR
END FUNCTION
Python implementation:
import time
import random
def retry_with_backoff(operation, max_retries=3, base_delay=1.0):
# FOR attempt FROM 0 TO max_retries - 1
for attempt in range(max_retries):
try:
# SET result TO operation()
result = operation()
# RETURN result (success)
return result
except Exception as error:
# IF attempt EQUALS max_retries - 1 THEN RAISE
if attempt == max_retries - 1:
raise
# SET delay TO base_delay * (2 ^ attempt)
delay = base_delay * (2 ** attempt)
# SET jitter TO random value between 0 and delay * 0.1
jitter = random.uniform(0, delay * 0.1)
# WAIT FOR delay + jitter seconds
time.sleep(delay + jitter)
# Test: operation that fails twice then succeeds
attempt_count = 0
def flaky_operation():
global attempt_count
attempt_count += 1
if attempt_count < 3:
raise ConnectionError(f"Failed on attempt {attempt_count}")
return "Success!"
result = retry_with_backoff(flaky_operation, max_retries=5, base_delay=0.01)
print(result)
print(f"Took {attempt_count} attempts")Production insight: The pseudocode made three critical design decisions explicit before we wrote any Python: (1) when to give up (last attempt check), (2) how to calculate delay (exponential formula), and (3) jitter to prevent thundering herd. These are exactly the things that cause bugs if you skip the design step.
import time
import random
def retry_with_backoff(operation, max_retries=3, base_delay=1.0):
# Design pseudocode first, then implement
# operation() may raise an exception
# Return the result on success, or raise the last exception
pass
# Test: operation that fails twice then succeeds
attempt_count = 0
def flaky_operation():
global attempt_count
attempt_count += 1
if attempt_count < 3:
raise ConnectionError(f"Failed on attempt {attempt_count}")
return "Success!"
result = retry_with_backoff(flaky_operation, max_retries=5, base_delay=0.01)
print(result)
print(f"Took {attempt_count} attempts")Expected Output
Success!\nTook 3 attemptsHints
Hint 1: Exponential backoff means each retry waits longer: delay = base_delay * (2 ^ attempt_number). Add a small random jitter to avoid thundering herd.
Hint 2: Use a for loop from 0 to max_retries-1. Wrap the operation call in try/except. If it succeeds, return immediately. If it fails on the last attempt, re-raise.
Write pseudocode for a password validator that checks all four rules and collects all violations (not just the first one):
- Minimum 8 characters
- At least one uppercase letter
- At least one digit
- At least one special character (
!@#$%^&*()_+-=)
Return a tuple of Pseudocode: Python implementation: Design lesson: The pseudocode made a key UX decision explicit: check all rules and collect all errors, rather than returning on the first failure. This is the difference between a frustrating validator ("fix this... now fix this other thing... now fix this too...") and a helpful one. The pseudocode stage is where you make these decisions.(is_valid, error_list).Solution
def validate_password(password):
# SET errors TO empty list
errors = []
# SET special_chars TO "!@#$%^&*()_+-="
special_chars = "!@#$%^&*()_+-="
# IF length of password < 8
if len(password) < 8:
errors.append("Too short (min 8 characters)")
# SET flags TO false
has_upper = False
has_digit = False
has_special = False
# FOR EACH char IN password
for char in password:
if char.isupper():
has_upper = True
if char.isdigit():
has_digit = True
if char in special_chars:
has_special = True
# Check each flag, append error if false
if not has_upper:
errors.append("No uppercase letter")
if not has_digit:
errors.append("No digit")
if not has_special:
errors.append("No special character")
# SET is_valid TO (errors is empty)
is_valid = len(errors) == 0
return (is_valid, errors)
result1 = validate_password("Str0ng!Pass")
print(result1)
result2 = validate_password("weak")
print(result2)
result3 = validate_password("NoDigitsHere!")
print(result3)
def validate_password(password):
# Design pseudocode first, then implement
# Return (is_valid: bool, errors: list of strings)
pass
result1 = validate_password("Str0ng!Pass")
print(result1)
result2 = validate_password("weak")
print(result2)
result3 = validate_password("NoDigitsHere!")
print(result3)Expected Output
(True, [])\n(False, ['Too short (min 8 characters)', 'No uppercase letter', 'No digit', 'No special character'])\n(False, ['No digit'])Hints
Hint 1: Design your pseudocode to check four conditions independently (not short-circuit). Collect all errors in a list so the user sees everything wrong at once.
Hint 2: For special characters, define a set like "!@#$%^&*()_+-=" and check if any character in the password belongs to it.
Design pseudocode for a token bucket rate limiter — a classic system design component. Then implement it as a Python class.
How it works:
- The bucket holds up to
capacitytokens, starting full - Tokens are added at
refill_ratetokens per second - Each request consumes 1 token — allowed if tokens available, denied otherwise
Solution
Pseudocode:
CLASS TokenBucket
CONSTRUCTOR(capacity, refill_rate)
SET self.capacity TO capacity
SET self.refill_rate TO refill_rate
SET self.tokens TO capacity (start full)
SET self.last_refill_time TO current time
END CONSTRUCTOR
METHOD allow_request()
CALL refill()
IF self.tokens >= 1 THEN
DECREMENT self.tokens BY 1
RETURN true
ELSE
RETURN false
END IF
END METHOD
METHOD refill()
SET now TO current time
SET elapsed TO now - self.last_refill_time
SET new_tokens TO elapsed * self.refill_rate
SET self.tokens TO min(self.tokens + new_tokens, self.capacity)
SET self.last_refill_time TO now
END METHOD
END CLASS
Python implementation:
import time
class TokenBucket:
def __init__(self, capacity, refill_rate):
# SET self.capacity, refill_rate
self.capacity = capacity
self.refill_rate = refill_rate
# SET self.tokens TO capacity (start full)
self.tokens = capacity
# SET self.last_refill_time TO current time
self.last_refill_time = time.monotonic()
def _refill(self):
# SET now TO current time
now = time.monotonic()
# SET elapsed TO now - self.last_refill_time
elapsed = now - self.last_refill_time
# SET new_tokens TO elapsed * self.refill_rate
new_tokens = elapsed * self.refill_rate
# SET self.tokens TO min(tokens + new_tokens, capacity)
self.tokens = min(self.tokens + new_tokens, self.capacity)
# SET self.last_refill_time TO now
self.last_refill_time = now
def allow_request(self):
# CALL refill
self._refill()
# IF self.tokens >= 1
if self.tokens >= 1:
self.tokens -= 1
return True
else:
return False
# Test
bucket = TokenBucket(capacity=3, refill_rate=1)
results = []
for i in range(5):
results.append(bucket.allow_request())
print(results)
# Wait for refill
time.sleep(0.05)
bucket2 = TokenBucket(capacity=2, refill_rate=100)
print(bucket2.allow_request()) # True
print(bucket2.allow_request()) # True
print(bucket2.allow_request()) # False (bucket empty)
time.sleep(0.02) # wait for ~2 tokens
print(bucket2.allow_request()) # True (refilled)System design insight: The pseudocode separated the rate limiter into two concerns — refill logic and request logic. This separation made the implementation clean: _refill() handles the time math, allow_request() handles the token check. In a real system, you would also need thread safety (a lock around _refill and token decrement), but the pseudocode design phase is where you identify that need.
import time
class TokenBucket:
def __init__(self, capacity, refill_rate):
# capacity: max tokens in the bucket
# refill_rate: tokens added per second
pass
def allow_request(self):
# Return True if request is allowed, False otherwise
pass
# Test
bucket = TokenBucket(capacity=3, refill_rate=1)
results = []
for i in range(5):
results.append(bucket.allow_request())
print(results)
# Wait for refill
time.sleep(0.05) # small sleep for test speed
bucket2 = TokenBucket(capacity=2, refill_rate=100) # fast refill for testing
print(bucket2.allow_request()) # True
print(bucket2.allow_request()) # True
print(bucket2.allow_request()) # False (bucket empty)
time.sleep(0.02) # wait for ~2 tokens
print(bucket2.allow_request()) # True (refilled)Expected Output
[True, True, True, False, False]\nTrue\nTrue\nFalse\nTrueHints
Hint 1: The bucket starts full. Each request removes one token. Tokens refill over time based on elapsed seconds since last check.
Hint 2: In allow_request: first calculate how many tokens to add based on elapsed time, then cap at capacity, then check if tokens >= 1.
Hard
Write pseudocode for an LRU (Least Recently Used) Cache, then implement it using Python's OrderedDict. This is a top interview question at every major tech company.
Requirements:
get(key)— return value if exists (and mark as recently used), else return -1put(key, value)— insert or update (and mark as recently used). If over capacity, evict the least recently used entry.- Both operations must be O(1).
Solution
Pseudocode:
CLASS LRUCache
CONSTRUCTOR(capacity)
SET self.capacity TO capacity
SET self.cache TO new OrderedDict (maintains insertion order)
END CONSTRUCTOR
METHOD get(key)
IF key NOT IN self.cache THEN
RETURN -1
END IF
MOVE key TO end of self.cache (mark as most recently used)
RETURN self.cache[key]
END METHOD
METHOD put(key, value)
IF key IN self.cache THEN
MOVE key TO end of self.cache (mark as most recently used)
SET self.cache[key] TO value
ELSE
IF length of self.cache >= self.capacity THEN
REMOVE first item from self.cache (least recently used)
END IF
SET self.cache[key] TO value (added at end = most recent)
END IF
END METHOD
END CLASS
Python implementation:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
# SET self.capacity and self.cache
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
# IF key NOT IN self.cache THEN RETURN -1
if key not in self.cache:
return -1
# MOVE key TO end (mark as most recently used)
self.cache.move_to_end(key)
# RETURN self.cache[key]
return self.cache[key]
def put(self, key, value):
# IF key IN self.cache (update existing)
if key in self.cache:
# MOVE key TO end (mark as most recently used)
self.cache.move_to_end(key)
self.cache[key] = value
else:
# IF over capacity, REMOVE first item (LRU)
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
# SET self.cache[key] TO value
self.cache[key] = value
# Test
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
print(cache.get("a")) # 1 (a is now most recently used)
cache.put("c", 3) # evicts "b" (least recently used)
print(cache.get("b")) # -1 (evicted)
print(cache.get("c")) # 3
cache.put("d", 4) # evicts "a"
print(cache.get("a")) # -1 (evicted)
print(cache.get("c")) # 3
print(cache.get("d")) # 4Why pseudocode matters here: The LRU cache has a subtle invariant — the "end" of the ordered dict is always the most recently used, and the "front" is the least recently used. The pseudocode made this ordering strategy explicit with MOVE key TO end. Without this design step, it is easy to get the eviction direction wrong (removing the wrong end).
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
pass
def get(self, key):
# Return value if key exists, else -1
pass
def put(self, key, value):
# Insert or update. Evict least-recently-used if over capacity.
pass
# Test
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
print(cache.get("a")) # 1 (a is now most recently used)
cache.put("c", 3) # evicts "b" (least recently used)
print(cache.get("b")) # -1 (evicted)
print(cache.get("c")) # 3
cache.put("d", 4) # evicts "a"
print(cache.get("a")) # -1 (evicted)
print(cache.get("c")) # 3
print(cache.get("d")) # 4Expected Output
1\n-1\n3\n-1\n3\n4Hints
Hint 1: OrderedDict remembers insertion order. The key operation is `move_to_end(key)` — call it on every get and put to mark the key as most recently used.
Hint 2: When the cache exceeds capacity, call `popitem(last=False)` to remove the first (oldest/least-recently-used) item.
Design pseudocode for a state machine that models a traffic light with normal cycling and an emergency mode. Then implement it.
States: GREEN → YELLOW → RED → GREEN (normal cycle), plus FLASHING_RED (emergency).
Rules:
next()advances through the normal cycle (GREEN → YELLOW → RED → GREEN)handle_emergency()enters FLASHING_RED from any state- In FLASHING_RED,
next()does nothing (stays in FLASHING_RED) resume()returns to RED (the safest state to resume from)
Solution
Pseudocode:
CLASS TrafficLight
DEFINE transitions AS:
"GREEN" -> "YELLOW"
"YELLOW" -> "RED"
"RED" -> "GREEN"
"FLASHING_RED" -> "FLASHING_RED" (no transition)
CONSTRUCTOR()
SET self.state TO "GREEN"
END CONSTRUCTOR
METHOD get_state()
RETURN self.state
END METHOD
METHOD next()
SET self.state TO transitions[self.state]
END METHOD
METHOD handle_emergency()
SET self.state TO "FLASHING_RED"
END METHOD
METHOD resume()
IF self.state EQUALS "FLASHING_RED" THEN
SET self.state TO "RED" (safest state to resume)
END IF
END METHOD
END CLASS
Python implementation:
class TrafficLight:
# DEFINE transitions
TRANSITIONS = {
"GREEN": "YELLOW",
"YELLOW": "RED",
"RED": "GREEN",
"FLASHING_RED": "FLASHING_RED", # no transition in emergency
}
def __init__(self):
# SET self.state TO "GREEN"
self.state = "GREEN"
def get_state(self):
# RETURN self.state
return self.state
def next(self):
# SET self.state TO transitions[self.state]
self.state = self.TRANSITIONS[self.state]
def handle_emergency(self):
# SET self.state TO "FLASHING_RED"
self.state = "FLASHING_RED"
def resume(self):
# IF self.state EQUALS "FLASHING_RED"
if self.state == "FLASHING_RED":
# SET self.state TO "RED" (safest state to resume)
self.state = "RED"
# Test normal cycle
light = TrafficLight()
print(light.get_state()) # GREEN
light.next()
print(light.get_state()) # YELLOW
light.next()
print(light.get_state()) # RED
light.next()
print(light.get_state()) # GREEN
# Test emergency
light.handle_emergency()
print(light.get_state()) # FLASHING_RED
light.next() # should stay in FLASHING_RED
print(light.get_state()) # FLASHING_RED
light.resume()
print(light.get_state()) # REDState machine design lesson: The pseudocode captured the entire system in a single transition table — a dictionary mapping current state to next state. This is the canonical way to implement state machines: data-driven transitions instead of nested if/else chains. The pseudocode design phase is where you realize that FLASHING_RED should map to itself (no transition), and that resume should go to RED (not back to the previous state, which could be dangerous).
class TrafficLight:
def __init__(self):
pass
def get_state(self):
# Return current state as string
pass
def next(self):
# Advance to next state
pass
def handle_emergency(self):
# Switch to flashing red mode
pass
def resume(self):
# Return to normal operation from emergency mode
pass
# Test normal cycle
light = TrafficLight()
print(light.get_state()) # GREEN
light.next()
print(light.get_state()) # YELLOW
light.next()
print(light.get_state()) # RED
light.next()
print(light.get_state()) # GREEN
# Test emergency
light.handle_emergency()
print(light.get_state()) # FLASHING_RED
light.next() # should stay in FLASHING_RED
print(light.get_state()) # FLASHING_RED
light.resume()
print(light.get_state()) # REDExpected Output
GREEN\nYELLOW\nRED\nGREEN\nFLASHING_RED\nFLASHING_RED\nREDHints
Hint 1: Define the transitions as a dictionary mapping each state to the next state. FLASHING_RED is a special state that does not transition on next().
Hint 2: For resume(), the state machine should return to RED (the safest state) rather than wherever it was before the emergency.
Write pseudocode for merge sort — the classic divide-and-conquer sorting algorithm — then implement it with comments that map each line back to your pseudocode.
This is a two-part design challenge:
- The recursive
merge_sortfunction (split and recurse) - The
mergehelper function (combine two sorted lists)
Solution
Pseudocode:
FUNCTION merge_sort(arr)
--- Base case ---
IF length of arr <= 1 THEN
RETURN arr
END IF
--- Split ---
SET mid TO length of arr // 2
SET left_half TO merge_sort(arr[0 .. mid])
SET right_half TO merge_sort(arr[mid .. end])
--- Merge ---
RETURN merge(left_half, right_half)
END FUNCTION
FUNCTION merge(left, right)
SET result TO empty list
SET i TO 0 (pointer for left)
SET j TO 0 (pointer for right)
--- Compare and merge ---
WHILE i < length of left AND j < length of right
IF left[i] <= right[j] THEN
APPEND left[i] TO result
INCREMENT i
ELSE
APPEND right[j] TO result
INCREMENT j
END IF
END WHILE
--- Append remaining elements ---
APPEND left[i .. end] TO result
APPEND right[j .. end] TO result
RETURN result
END FUNCTION
Python implementation:
def merge_sort(arr):
# --- Base case ---
# IF length of arr <= 1 THEN RETURN arr
if len(arr) <= 1:
return arr
# --- Split ---
# SET mid TO length of arr // 2
mid = len(arr) // 2
# SET left_half TO merge_sort(arr[0 .. mid])
left_half = merge_sort(arr[:mid])
# SET right_half TO merge_sort(arr[mid .. end])
right_half = merge_sort(arr[mid:])
# --- Merge ---
# RETURN merge(left_half, right_half)
return merge(left_half, right_half)
def merge(left, right):
# SET result TO empty list
result = []
# SET i TO 0 (pointer for left)
i = 0
# SET j TO 0 (pointer for right)
j = 0
# --- Compare and merge ---
# WHILE i < length of left AND j < length of right
while i < len(left) and j < len(right):
# IF left[i] <= right[j]
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# --- Append remaining elements ---
# APPEND left[i .. end] TO result
result.extend(left[i:])
# APPEND right[j .. end] TO result
result.extend(right[j:])
# RETURN result
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
print(merge_sort([5, 1]))
print(merge_sort([1]))
print(merge_sort([]))
print(merge_sort([4, 4, 2, 2, 1, 1]))Divide-and-conquer insight: The pseudocode forced us to separate the algorithm into two distinct responsibilities: merge_sort handles the recursive splitting, merge handles combining sorted halves. Every line of pseudocode maps directly to Python. Notice how <= in the merge comparison (not <) preserves stability — equal elements keep their original relative order. This is a detail that is easy to get wrong without thinking through the pseudocode first.
def merge_sort(arr):
# Design pseudocode first
# Implement with comments mapping back to pseudocode steps
pass
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
print(merge_sort([5, 1]))
print(merge_sort([1]))
print(merge_sort([]))
print(merge_sort([4, 4, 2, 2, 1, 1]))Expected Output
[3, 9, 10, 27, 38, 43, 82]\n[1, 5]\n[1]\n[]\n[1, 1, 2, 2, 4, 4]Hints
Hint 1: Merge sort has two phases: (1) recursively split the list in half until you have single elements, (2) merge two sorted halves back together. Write pseudocode for both the split step and the merge step separately.
Hint 2: The merge step uses two pointers (i for left, j for right). Compare left[i] vs right[j], take the smaller one, advance that pointer. When one side is exhausted, append the remainder of the other.