Python Sorting Mechanisms Practice Problems & Exercises

Practice: Sorting Mechanisms

11 problems4 Easy4 Medium3 Hard⏱ 40-55 min

← Back to lesson

---

#1Sort Without Losing Your ListEasy

sorted() vs sort()return value

Given a list of integers, return a new sorted list in ascending order. The original list must remain unchanged.

Constraints:

• Do not mutate the input list
• Return a new list object

Solution

def sort_safely(numbers):
    return sorted(numbers)

# Test
original = [5, 2, 8, 1, 9]
result = sort_safely(original)
print(f"Original: {original}")
print(f"Sorted:   {result}")
print(f"Original unchanged: {original == [5, 2, 8, 1, 9]}")

Key insight: sorted() always returns a new list. list.sort() returns None and modifies the list in place. Writing data = data.sort() is a classic Python bug that sets data to None.

Starter Code

def sort_safely(numbers):
  """Return a new sorted list without modifying the original.

  Args:
      numbers: list of integers
  Returns:
      A new list with elements sorted ascending
  """
  # TODO: return a sorted copy — do NOT modify 'numbers'
  pass

Expected Output

Original: [5, 2, 8, 1, 9]
Sorted:   [1, 2, 5, 8, 9]
Original unchanged: True

Hints

Hint 1: list.sort() modifies the list in place and returns None — that is not what you want here.

Hint 2: sorted() returns a new list and leaves the original untouched.

---

#2Case-Insensitive SortEasy

key functionstr.lower

Sort a list of strings alphabetically without regard to upper/lower case. The original casing of each string must be preserved in the output.

Example: ["Date", "apple", "cherry", "Banana"] becomes ["apple", "Banana", "cherry", "Date"]

Solution

def sort_case_insensitive(words):
    return sorted(words, key=str.lower)

# Test
result = sort_case_insensitive(["Date", "apple", "cherry", "Banana"])
print(result)

Key insight: The key function transforms each element for comparison only. The actual elements in the output retain their original form. str.lower is a built-in method reference — no need for a lambda.

Starter Code

def sort_case_insensitive(words):
  """Sort strings alphabetically, ignoring case.

  Args:
      words: list of strings
  Returns:
      New list sorted case-insensitively (original case preserved)
  """
  # TODO: sort ignoring case — 'apple' and 'Apple' are treated the same
  pass

Expected Output

['apple', 'Banana', 'cherry', 'Date']

Hints

Hint 1: Default string sort uses Unicode code points — uppercase letters (A=65) sort before lowercase (a=97).

Hint 2: Use the key parameter with str.lower to compare lowercase versions while preserving original case.

---

#3Sort Dictionary by ValueEasy

dict sortingitems()key function

Given a dictionary mapping names to scores, return a new dictionary sorted by score. Support both ascending and descending order.

Example: sort_dict_by_value(scores, descending=True) returns highest scores first.

Solution

def sort_dict_by_value(d, descending=False):
    sorted_items = sorted(d.items(), key=lambda x: x[1], reverse=descending)
    return dict(sorted_items)

# Test
scores = {"alice": 95, "bob": 80, "carol": 88, "dave": 72}
print(f"Ascending:  {sort_dict_by_value(scores)}")
print(f"Descending: {sort_dict_by_value(scores, descending=True)}")

Key insight: d.items() yields (key, value) tuples. lambda x: x[1] extracts the value for comparison. dict() on a list of tuples preserves insertion order in Python 3.7+.

Starter Code

def sort_dict_by_value(d, descending=False):
  """Sort a dictionary by its values and return an ordered dict.

  Args:
      d: dictionary with string keys and numeric values
      descending: if True, sort highest value first
  Returns:
      A new dict sorted by value
  """
  # TODO: sort dict items by value, return a new dict
  pass

Expected Output

Ascending:  {'dave': 72, 'bob': 80, 'carol': 88, 'alice': 95}
Descending: {'alice': 95, 'carol': 88, 'bob': 80, 'dave': 72}

Hints

Hint 1: Use d.items() to get (key, value) pairs, then sorted() with a key function that extracts the value.

Hint 2: Pass the sorted list of tuples to dict() to reconstruct an ordered dictionary (Python 3.7+ preserves insertion order).

---

#4Sort with None ValuesEasy

None handlingkey functionedge cases

Sort a list of integers that may contain None values. Python 3 raises TypeError if you try to sort a list containing None alongside integers. Handle this gracefully by placing None values at the end or beginning based on the nones_last parameter.

Example: [3, None, 1, None, 5, 2] with nones_last=True becomes [1, 2, 3, 5, None, None]

Solution

def sort_with_nones(data, nones_last=True):
    if nones_last:
        return sorted(data, key=lambda x: (x is None, x if x is not None else 0))
    else:
        return sorted(data, key=lambda x: (x is not None, x if x is not None else 0))

# Test
values = [3, None, 1, None, 5, 2]
print(f"Nones last:  {sort_with_nones(values, nones_last=True)}")
print(f"Nones first: {sort_with_nones(values, nones_last=False)}")

Key insight: The tuple key (x is None, value) works because Python compares tuples element by element. False (0) sorts before True (1), so (False, 3) comes before (True, 0), pushing None to the end. Flip the boolean to push None to the front.

Starter Code

def sort_with_nones(data, nones_last=True):
  """Sort a list of integers that may contain None values.

  Args:
      data: list of integers and None values
      nones_last: if True, put None at end; if False, put None at start
  Returns:
      New sorted list with None values placed as specified
  """
  # TODO: sort handling None without raising TypeError
  pass

Expected Output

Nones last:  [1, 2, 3, 5, None, None]
Nones first: [None, None, 1, 2, 3, 5]

Hints

Hint 1: Python 3 raises TypeError when comparing None to int. You need a key function that handles None.

Hint 2: Use a tuple key: (is_none_flag, actual_value). Since False (0) sorts before True (1), setting the flag to (x is None) pushes None to the end.

---

#5Multi-Key Employee SortMedium

tuple keymulti-key sortingnegation trick

Sort a list of employee dictionaries by three criteria simultaneously:

1. Department — ascending (alphabetical)
2. Salary — descending (highest first within each department)
3. Name — ascending (alphabetical for ties)

Use a single sort call with a tuple key.

Solution

def sort_employees(employees):
    return sorted(employees, key=lambda e: (e["dept"], -e["salary"], e["name"]))

# Test
employees = [
    {"name": "Alice", "dept": "Engineering", "salary": 95000},
    {"name": "Bob",   "dept": "Marketing",   "salary": 80000},
    {"name": "Carol", "dept": "Engineering", "salary": 110000},
    {"name": "Dave",  "dept": "Marketing",   "salary": 80000},
    {"name": "Eve",   "dept": "Engineering", "salary": 95000},
]

for e in sort_employees(employees):
    print(f"{e['dept']:13s} {e['salary']:>7d}  {e['name']}")

Key insight: Negating a numeric field (-e["salary"]) reverses its sort direction within a tuple key. This only works for numeric types. For non-numeric descending sorts, you need the multi-pass stable sort approach.

Starter Code

def sort_employees(employees):
  """Sort employees by department (asc), salary (desc), name (asc).

  Args:
      employees: list of dicts with 'name', 'dept', 'salary' keys
  Returns:
      New sorted list of employee dicts
  """
  # TODO: single sort with tuple key
  pass

Expected Output

Engineering  110000  Carol
Engineering   95000  Alice
Engineering   95000  Eve
Marketing     80000  Bob
Marketing     80000  Dave

Hints

Hint 1: Use a tuple key: (dept, -salary, name). Negating salary makes higher salaries sort first.

Hint 2: This works because Python compares tuples lexicographically — first by dept, then by -salary for ties, then by name.

---

#6Stable Sort ProofMedium

sort stabilitymulti-pass sorting

Sort a list of records by category (ascending) and then by priority (descending within each category). You must use two separate sort passes to demonstrate that Python's sort stability makes multi-pass sorting correct. Do NOT use a tuple key.

Input:

records = [
    {"item": "item_a", "category": "A", "priority": 1},
    {"item": "item_b", "category": "B", "priority": 2},
    {"item": "item_c", "category": "A", "priority": 3},
    {"item": "item_d", "category": "B", "priority": 2},
]

Notice that item_b and item_d have equal priority — stable sort preserves their original relative order.

Solution

def stable_multi_sort(records):
    # Step 1: sort by SECONDARY key first (priority descending)
    result = sorted(records, key=lambda r: r["priority"], reverse=True)
    # Step 2: sort by PRIMARY key last (category ascending)
    result.sort(key=lambda r: r["category"])
    return result

# Test
records = [
    {"item": "item_a", "category": "A", "priority": 1},
    {"item": "item_b", "category": "B", "priority": 2},
    {"item": "item_c", "category": "A", "priority": 3},
    {"item": "item_d", "category": "B", "priority": 2},
]

for r in stable_multi_sort(records):
    print(f"{r['category']}  {r['priority']}  {r['item']}")

Key insight: The order of sort passes matters. Sort secondary key first, primary key last. Because stable sort preserves relative order among equal elements, the secondary ordering survives the primary sort. item_b stays before item_d (same priority, original order preserved).

Starter Code

def stable_multi_sort(records):
  """Sort records by category (asc), then by priority (desc) using
  two separate stable sort passes (NOT a tuple key).

  Args:
      records: list of dicts with 'item', 'category', 'priority'
  Returns:
      Sorted list demonstrating stable sort behavior
  """
  # TODO: two-pass stable sort — which key do you sort FIRST?
  pass

Expected Output

A  3  item_c
A  1  item_a
B  2  item_b
B  2  item_d

Hints

Hint 1: For multi-pass stable sorting, sort by the SECONDARY criterion first, then by the PRIMARY criterion last.

Hint 2: The last sort is the primary grouping. Because Python sort is stable, the secondary ordering is preserved within each primary group.

---

#7Sort Strings by Multiple CriteriaMedium

key functionlen()tuple key

Sort a list of strings first by length (shortest first), then alphabetically among strings of the same length.

Example: ["to", "be", "or", "not", "that", "the", "art", "go"]

Strings of length 2: be, go, or, to (sorted alphabetically). Strings of length 3: art, not, the. Strings of length 4: that.

Solution

def sort_strings_complex(words):
    return sorted(words, key=lambda w: (len(w), w))

# Test
words = ["to", "be", "or", "not", "that", "the", "art", "go"]
result = sort_strings_complex(words)
print(result)
# ['be', 'go', 'or', 'to', 'art', 'not', 'the', 'that']

Key insight: Tuple keys are compared lexicographically. (2, 'be') comes before (2, 'go') because the first elements are equal and 'be' < 'go'. (2, 'to') comes before (3, 'art') because 2 < 3 regardless of the second element.

Starter Code

def sort_strings_complex(words):
  """Sort strings by length (shortest first), then alphabetically for ties.

  Args:
      words: list of strings
  Returns:
      New sorted list
  """
  # TODO: sort by length first, then alphabetically
  pass

Expected Output

['be', 'go', 'to', 'art', 'not', 'or', 'that', 'the']
Wait — check the expected output carefully!

Hints

Hint 1: Use a tuple key: (len(word), word) — Python will sort by length first, then by string value for ties.

Hint 2: Remember that string comparison is lexicographic — 'be' comes before 'go' comes before 'to'.

---

#8Implement Bubble SortMedium

sorting algorithmsbubble sortimplementation

Implement the bubble sort algorithm from scratch. Include the early-exit optimization: if a pass completes without any swaps, the list is already sorted and you can stop.

This is O(n^2) worst case but O(n) best case (already sorted) with the optimization.

Solution

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # Already sorted — O(n) best case

# Test
data = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(data)
print(data)

Key insight: The early-exit optimization makes bubble sort O(n) on already-sorted input, similar to Timsort's run detection. Without the optimization, bubble sort always runs O(n^2). In practice, Python's built-in Timsort is dramatically faster for all inputs — this is an educational exercise, not a production pattern.

Starter Code

def bubble_sort(arr):
  """Sort a list in-place using the bubble sort algorithm.

  - Compare adjacent elements and swap if out of order
  - Repeat passes until no swaps occur
  - Optimize: after each pass, the last element is in its final position

  Args:
      arr: list of comparable elements (modified in-place)
  Returns:
      None (sorts in-place, like list.sort())
  """
  # TODO: implement bubble sort with early-exit optimization
  pass

Expected Output

[1, 1, 2, 3, 4, 5, 6, 9]

Hints

Hint 1: Outer loop runs n-1 times. Inner loop compares arr[j] with arr[j+1] and swaps if arr[j] > arr[j+1].

Hint 2: Track whether any swap happened in the current pass. If no swaps occurred, the list is sorted — break early.

Hint 3: After pass i, the last i+1 elements are already in their final positions, so the inner loop can shrink.

---

#9Implement Insertion SortHard

sorting algorithmsinsertion sortTimsort building block

Implement insertion sort with support for sorting a subarray (by specifying left and right indices). This is exactly how Timsort handles short runs — it uses insertion sort on small segments before merging them.

Why this matters: Timsort extends short runs to minrun length using insertion sort because insertion sort has very low overhead for small arrays and is cache-friendly.

Solution

def insertion_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Test — full sort
data = [3, 1, 4, 1, 5, 9, 2, 6]
insertion_sort(data)
print(f"Full sort: {data}")

# Test — partial sort (only indices 2 through 5)
data2 = [3, 1, 9, 5, 4, 1, 2, 6]
insertion_sort(data2, left=2, right=5)
print(f"Partial sort (indices 2-5): {data2}")

Key insight: Insertion sort is O(n^2) worst case but O(n) on nearly-sorted data, and it has very low constant overhead. Timsort uses it for runs shorter than minrun (typically 32-64 elements) because the overhead of merge sort is not worth it for small arrays. The subarray support (left/right parameters) mirrors how Timsort invokes it internally.

Starter Code

def insertion_sort(arr, left=0, right=None):
  """Sort a subarray in-place using insertion sort.

  This is the same algorithm Timsort uses for small runs.

  Args:
      arr: list of comparable elements
      left: start index of subarray (inclusive)
      right: end index of subarray (inclusive). Defaults to last element.
  Returns:
      None (sorts in-place)
  """
  # TODO: implement insertion sort on arr[left..right]
  pass

Expected Output

Full sort: [1, 1, 2, 3, 4, 5, 6, 9]
Partial sort (indices 2-5): [3, 1, 1, 4, 5, 9, 2, 6]

Hints

Hint 1: For each element from left+1 to right, save the current value as 'key'. Shift all larger elements one position right, then insert the key.

Hint 2: The inner while loop moves backward from the current position, shifting elements right until it finds the correct insertion point.

Hint 3: The right parameter defaults to len(arr)-1 if not provided. This allows sorting a subarray, which is exactly what Timsort does for short runs.

---

#10Leaderboard Ranking SystemHard

multi-key sortingNone handlingtuple keyproduction pattern

Build a competitive programming leaderboard ranker. This combines multiple sorting techniques from the lesson: tuple keys, negation for descending, None handling, and stability.

Test data:

entries = [
    {"user": "alice", "solved": 3, "penalty": 240, "last_sub": 180},
    {"user": "bob",   "solved": 3, "penalty": 240, "last_sub": 120},
    {"user": "carol", "solved": 5, "penalty": 180, "last_sub": 300},
    {"user": "dave",  "solved": 0, "penalty": None, "last_sub": 0},
    {"user": "eve",   "solved": 3, "penalty": 200, "last_sub": 150},
    {"user": "frank", "solved": 0, "penalty": None, "last_sub": 0},
]

Solution

def rank_leaderboard(entries):
    def sort_key(e):
        no_solutions = (e["solved"] == 0)
        penalty_val = e["penalty"] if e["penalty"] is not None else 0
        return (
            -e["solved"],
            (no_solutions, penalty_val),
            e["last_sub"],
            e["user"],
        )

    ranked = sorted(entries, key=sort_key)
    results = []
    for i, e in enumerate(ranked, 1):
        penalty_str = str(e["penalty"]) if e["penalty"] is not None else "N/A"
        results.append((i, e["user"], e["solved"], penalty_str))
    return results

# Test
entries = [
    {"user": "alice", "solved": 3, "penalty": 240, "last_sub": 180},
    {"user": "bob",   "solved": 3, "penalty": 240, "last_sub": 120},
    {"user": "carol", "solved": 5, "penalty": 180, "last_sub": 300},
    {"user": "dave",  "solved": 0, "penalty": None, "last_sub": 0},
    {"user": "eve",   "solved": 3, "penalty": 200, "last_sub": 150},
    {"user": "frank", "solved": 0, "penalty": None, "last_sub": 0},
]

for rank, user, solved, penalty in rank_leaderboard(entries):
    print(f"{rank}. {user:7s} - {solved} solved, penalty {penalty}")

Key insight: The tuple (no_solutions, penalty_val) is the critical trick. Since True > False in Python, (True, 0) sorts after (False, any_number), pushing zero-solve users to the bottom. This avoids the TypeError from comparing None directly.

Starter Code

def rank_leaderboard(entries):
  """Rank competitive programming contestants.

  Ranking criteria (in order of priority):
  1. Problems solved — descending (more is better)
  2. Penalty time — ascending (less is better)
  3. Last submission time — ascending (earlier is better)
  4. Username — ascending (alphabetical tiebreak)

  Users with 0 problems solved have penalty=None.
  They sort to the bottom regardless of other fields.

  Args:
      entries: list of dicts with 'user', 'solved', 'penalty', 'last_sub'
  Returns:
      List of (rank, user, solved, penalty) tuples
  """
  # TODO: build the sort key that handles all 4 criteria + None
  pass

Expected Output

1. carol   - 5 solved, penalty 180
2. eve     - 3 solved, penalty 200
3. bob     - 3 solved, penalty 240
4. alice   - 3 solved, penalty 240
5. dave    - 0 solved, penalty N/A
6. frank   - 0 solved, penalty N/A

Hints

Hint 1: Negate 'solved' to sort descending. Use a tuple (no_solutions_flag, penalty_or_zero) to push None-penalty users to the bottom.

Hint 2: The key function returns a tuple: (-solved, (solved==0, penalty or 0), last_sub, user). Since True > False, users with solved==0 sort after everyone else.

Hint 3: Users with equal 'solved' and 'penalty' are differentiated by 'last_sub' (earlier is better), then by 'user' (alphabetical).

---

#11Implement Merge Sort with Stability ProofHard

merge sortstabilitysorting algorithmsdivide and conquer

Implement merge sort from scratch with a focus on stability. Then write a function that proves your implementation is stable by tagging elements with their original indices and verifying the ordering is preserved after sorting.

Why this matters: Stability is not automatic — it depends on the merge step always choosing the LEFT element when values are equal. An unstable merge sort takes from the right on ties, breaking relative order.

Test data: [5, 3, 2, 5, 2, 8, 3, 1] — contains three pairs of duplicates (5, 2, 3).

Solution

def merge_sort_stable(arr):
    if len(arr) <= 1:
        return arr[:]

    mid = len(arr) // 2
    left = merge_sort_stable(arr[:mid])
    right = merge_sort_stable(arr[mid:])

    # Merge — take from LEFT on ties to preserve stability
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # CRITICAL: use <= (not <) to take from left on equal values
        if left[i][0] <= right[j][0]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def prove_stability(data):
    # Tag each element with its original index
    tagged = [(val, idx) for idx, val in enumerate(data)]

    # Sort using our stable merge sort
    sorted_tagged = merge_sort_stable(tagged)

    # Extract sorted values
    sorted_values = [val for val, _ in sorted_tagged]

    # Check stability: for equal values, original indices must be ascending
    is_stable = True
    from collections import defaultdict
    groups = defaultdict(list)
    for val, orig_idx in sorted_tagged:
        groups[val].append(orig_idx)

    details = []
    for val in sorted(groups.keys()):
        indices = groups[val]
        if len(indices) > 1:
            ordered = all(indices[k] < indices[k+1] for k in range(len(indices)-1))
            if not ordered:
                is_stable = False
            details.append((val, indices, ordered))

    return sorted_values, is_stable, details


# Test
data = [5, 3, 2, 5, 2, 8, 3, 1]
sorted_values, is_stable, details = prove_stability(data)
print(f"Sorted: {sorted_values}")
print(f"Stable: {is_stable}")
for val, indices, ordered in details:
    status = "order preserved" if ordered else "ORDER VIOLATED"
    print(f"Detail: value={val} at original indices {indices} — {status}")

Key insight: The <= comparison in the merge step is the entire difference between a stable and unstable merge sort. Using < (strictly less than) would take from the right subarray on ties, breaking stability. Timsort's merge operation uses this same <= principle, which is why Python's sort is guaranteed stable.

Starter Code

def merge_sort_stable(arr):
  """Sort a list using merge sort, preserving stability.

  Stability rule: when two elements are equal, the one that
  appeared first in the original array must appear first in
  the result.

  Args:
      arr: list of (value, original_index) tuples
  Returns:
      New sorted list of (value, original_index) tuples
  """
  # TODO: implement merge sort
  # TODO: in the merge step, when left[i] == right[j],
  #       take from LEFT to preserve stability
  pass


def prove_stability(data):
  """Demonstrate that your merge sort is stable.

  Tag each element with its original index, sort, then verify
  that equal elements retained their original relative order.

  Args:
      data: list of integers (may contain duplicates)
  Returns:
      (sorted_values, is_stable) tuple
  """
  # TODO: tag elements, sort with merge_sort_stable, verify order
  pass

Expected Output

Sorted: [1, 2, 2, 3, 3, 5, 5, 8]
Stable: True
Detail: value=2 at original indices [2, 4] — order preserved
Detail: value=3 at original indices [1, 6] — order preserved
Detail: value=5 at original indices [0, 3] — order preserved

Hints

Hint 1: Merge sort: split the array in half, recursively sort each half, then merge. Base case: arrays of length 0 or 1 are already sorted.

Hint 2: The merge step is where stability lives. When comparing left[i] and right[j], if they are equal, always take from the LEFT subarray first. This preserves original order.

Hint 3: For prove_stability: tag each element as (value, original_index), sort, then check that for each group of equal values, the original indices are in ascending order.