Sorting Problems | Coding Interview Sorting Patterns Complete Guide

Introduction

In coding interviews, sorting is often the first step to solving problems. Whether organizing candidates by score/time, or preparing for greedy/binary search algorithms, sort and key functions express conditions elegantly.

---

1. Basic Sorting

Python Sorting

Choose between in-place sorting (sort) or creating a new list (sorted) based on whether you need to preserve the original.

# Ascending order
arr = [5, 2, 8, 1, 9]
arr.sort()
print(arr)  # [1, 2, 5, 8, 9]

# Descending order
arr.sort(reverse=True)
print(arr)  # [9, 8, 5, 2, 1]

# Return new list
arr = [5, 2, 8, 1, 9]
sorted_arr = sorted(arr)
print(arr)  # [5, 2, 8, 1, 9] (original preserved)
print(sorted_arr)  # [1, 2, 5, 8, 9]

Time Complexity

• sort(), sorted(): O(n log n) (Timsort)
• Stable sorting guaranteed

---

2. Custom Sorting

Key Functions

# Sort by absolute value
arr = [-5, -2, 1, 3, -8]
arr.sort(key=abs)
print(arr)  # [1, -2, 3, -5, -8]

# Sort by string length
words = ["apple", "pie", "banana"]
words.sort(key=len)
print(words)  # ["pie", "apple", "banana"]

# Sort tuples (by first element)
students = [(85, "Alice"), (90, "Bob"), (80, "Charlie")]
students.sort()
print(students)
# [(80, 'Charlie'), (85, 'Alice'), (90, 'Bob')]

Multi-Condition Sorting

# Score descending, name ascending
students = [
    ("Alice", 85),
    ("Bob", 90),
    ("Charlie", 85),
    ("David", 90)
]

students.sort(key=lambda x: (-x[1], x[0]))
print(students)
# [('Bob', 90), ('David', 90), ('Alice', 85), ('Charlie', 85)]

# Age ascending, name descending
people = [
    ("Alice", 30),
    ("Bob", 25),
    ("Charlie", 30),
]
people.sort(key=lambda x: (x[1], -ord(x[0][0])))

cmp_to_key

from functools import cmp_to_key

def compare(x, y):
    if x > y:
        return 1
    elif x < y:
        return -1
    else:
        return 0

arr = [5, 2, 8, 1]
arr.sort(key=cmp_to_key(compare))
print(arr)  # [1, 2, 5, 8]

---

3. Problem Solving

Problem 1: Largest Number

def largest_number(nums):
    """
    Concatenate numbers to form largest number
    [3, 30, 34, 5, 9] → "9534330"
    """
    from functools import cmp_to_key
    
    def compare(x, y):
        if x + y > y + x:
            return -1
        elif x + y < y + x:
            return 1
        else:
            return 0
    
    nums_str = list(map(str, nums))
    nums_str.sort(key=cmp_to_key(compare))
    
    result = ''.join(nums_str)
    return '0' if result[0] == '0' else result

print(largest_number([3, 30, 34, 5, 9]))  # "9534330"
print(largest_number([0, 0, 0]))  # "0"

Problem 2: H-Index

def h_index(citations):
    """
    Find h-index: h papers cited at least h times
    [3, 0, 6, 1, 5] → 3
    """
    citations.sort(reverse=True)
    
    h = 0
    for i, citation in enumerate(citations):
        if citation >= i + 1:
            h = i + 1
        else:
            break
    
    return h

print(h_index([3, 0, 6, 1, 5]))  # 3
print(h_index([10, 8, 5, 4, 3]))  # 4

Problem 3: Merge Intervals

def merge_intervals(intervals):
    """
    Merge overlapping intervals
    [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
    """
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        if current[0] <= last[1]:
            merged[-1] = [last[0], max(last[1], current[1])]
        else:
            merged.append(current)
    
    return merged

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))
# [[1, 6], [8, 10], [15, 18]]

Problem 4: Meeting Rooms

def max_meetings(meetings):
    """
    Maximum non-overlapping meetings
    [(1, 4), (3, 5), (0, 6), (5, 7)] → 3
    """
    meetings.sort(key=lambda x: x[1])  # Sort by end time
    
    count = 0
    last_end = 0
    
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)]
print(max_meetings(meetings))  # 4

---

4. Sorting Patterns

Pattern 1: Sort + Two Pointers

def two_sum_sorted(arr, target):
    """
    Sort then use two pointers to find sum
    """
    arr.sort()
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [arr[left], arr[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return None

print(two_sum_sorted([2, 7, 11, 15], 9))  # [2, 7]

Pattern 2: Sort + Binary Search

from bisect import bisect_left

def count_smaller(arr, target):
    """
    Sort then binary search
    """
    arr.sort()
    idx = bisect_left(arr, target)
    return idx

arr = [5, 2, 8, 1, 9]
print(count_smaller(arr, 6))  # 3 (1, 2, 5)

Pattern 3: Sort + Greedy

def assign_cookies(children, cookies):
    """
    Assign cookies to children (maximize satisfaction)
    """
    children.sort()
    cookies.sort()
    
    i = j = 0
    while i < len(children) and j < len(cookies):
        if cookies[j] >= children[i]:
            i += 1
        j += 1
    
    return i

children = [1, 2, 3]
cookies = [1, 1]
print(assign_cookies(children, cookies))  # 1

Pattern 4: Custom Comparator

from functools import cmp_to_key

def sort_by_custom_rule(arr):
    """
    Sort with custom comparison logic
    """
    def compare(x, y):
        # Custom logic here
        if some_condition(x, y):
            return -1
        elif other_condition(x, y):
            return 1
        else:
            return 0
    
    arr.sort(key=cmp_to_key(compare))
    return arr

---

5. Practical Tips

Sorting Debugging

def debug_sort(arr, key=None):
    """Print sorting process"""
    print("Original:", arr)
    sorted_arr = sorted(arr, key=key)
    print("Sorted:", sorted_arr)
    return sorted_arr

students = [("Alice", 85), ("Bob", 90), ("Charlie", 80)]
debug_sort(students, key=lambda x: x[1])

Performance Measurement

import time

arr = list(range(100000, 0, -1))

start = time.time()
arr.sort()
end = time.time()

print(f"Sort time: {(end - start) * 1000:.2f}ms")

Common Mistakes

# ❌ Wrong: Modifying while iterating
arr = [3, 1, 4, 1, 5]
# for i, val in enumerate(arr):
#     if val == 1:
#         arr.remove(val)  # Skips elements!

# ✅ Correct: Filter with list comprehension
arr = [x for x in arr if x != 1]

# ❌ Wrong: Sorting without key
words = ["apple", "Banana", "cherry"]
words.sort()  # ['Banana', 'apple', 'cherry'] (uppercase first)

# ✅ Correct: Case-insensitive
words.sort(key=str.lower)  # ['apple', 'Banana', 'cherry']

---

Summary

Key Points

1. Python Sorting: sort(), sorted(), key functions
2. Custom Sorting: lambda, cmp_to_key
3. Multi-Condition: Return tuple (condition1, condition2)
4. Usage Patterns: Two pointers, binary search, greedy
5. Time Complexity: O(n log n)

When to Sort

Problem Type	Approach	Reason
Find pairs	Sort + Two Pointers	O(n) after sort
Range queries	Sort + Binary Search	O(log n) search
Interval problems	Sort by start/end	Greedy selection
Frequency problems	Sort by count	Top-k elements

---

Recommended Problems

Beginner

• LeetCode 88: Merge Sorted Array
• LeetCode 242: Valid Anagram
• LeetCode 349: Intersection of Two Arrays

Intermediate

• LeetCode 56: Merge Intervals
• LeetCode 75: Sort Colors
• LeetCode 148: Sort List

Advanced

• LeetCode 315: Count of Smaller Numbers After Self
• LeetCode 327: Count of Range Sum
• LeetCode 493: Reverse Pairs

---

Related Posts

• Arrays and Lists | Essential Data Structures
• Sorting Algorithms | Bubble, Selection, Insertion Sort
• Binary Search | O(log n) Search Algorithm

---

Keywords

Sorting, Algorithm, Python sort, Custom Sorting, Key Function, Multi-Condition Sort, Coding Interview, Problem Solving, Time Complexity, Stable Sort