Python Sorting Algorithms Interview Guide
Bubble sort, insertion sort, selection sort, merge sort, quick sort, and sorting problems.
1. Common Sorting Interview Questions
●
How does bubble sort work?
●
How does insertion sort work?
●
How does selection sort work?
●
What is the difference between merge sort and quick sort?
●
Which sorting algorithms are stable?
●
What does in-place sorting mean?
●
What are the time complexities of common sorting algorithms?
●
When should you use Python built-in sort instead of writing your own?
●
How do you sort objects, tuples, or dictionaries using a key?
●
How do you sort in descending order?
Tip: In real Python code, use sorted() or [Link](). In interviews, implement sorting algorithms to show understanding of
loops, comparisons, recursion, and partitioning.
2. Python Built-in Sorting
sort() modifies the list in place
nums = [3, 1, 4, 2]
[Link]()
print(nums) # [1, 2, 3, 4]
sorted() returns a new list
nums = [3, 1, 4, 2]
result = sorted(nums)
print(nums) # [3, 1, 4, 2]
print(result) # [1, 2, 3, 4]
Sort with key
words = ["banana", "fig", "apple"]
[Link](key=len)
print(words) # ['fig', 'apple', 'banana']
pairs = [("a", 3), ("b", 1), ("c", 2)]
[Link](key=lambda x: x[1])
print(pairs) # [('b', 1), ('c', 2), ('a', 3)]
3. Complexity Cheat Sheet
Algorithm Best Average Worst Space Stable?
Bubble sort O(n) O(n^2) O(n^2) O(1) Yes
Selection sort O(n^2) O(n^2) O(n^2) O(1) No
Insertion sort O(n) O(n^2) O(n^2) O(1) Yes
Python Interview Notes Page 1
Algorithm Best Average Worst Space Stable?
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick sort O(n log n) O(n log n) O(n^2) O(log n) Usually no
Counting sort O(n + k) O(n + k) O(n + k) O(k) Can be
Python Timsort O(n) O(n log n) O(n log n) O(n) Yes
4. Simple Sorting Algorithms
Bubble sort
Bubble sort repeatedly compares adjacent values and swaps them if they are in the wrong order. After each pass, the
largest remaining value bubbles to the end.
def bubble_sort(nums):
n = len(nums)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
swapped = True
if not swapped:
break
return nums
Tip: Bubble sort is rarely used in real code, but it is easy to explain. Mention the swapped flag optimization.
Selection sort
Selection sort repeatedly finds the smallest element in the unsorted part and places it at the front.
def selection_sort(nums):
n = len(nums)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if nums[j] < nums[min_index]:
min_index = j
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums
Insertion sort
Insertion sort builds a sorted section one element at a time. It is very good for small or nearly sorted lists.
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
return nums
5. Divide and Conquer Sorting
Merge sort
Python Interview Notes Page 2
Merge sort divides the list into halves, sorts each half, then merges the sorted halves. It has predictable O(n log n) time.
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
[Link](left[i:])
[Link](right[j:])
return result
Quick sort
Quick sort chooses a pivot, partitions values around it, and recursively sorts the partitions. It is fast on average but can
be O(n^2) with bad pivots.
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
In-place quick sort partition
def quick_sort_in_place(nums):
def partition(low, high):
pivot = nums[high]
i = low
for j in range(low, high):
if nums[j] <= pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[high] = nums[high], nums[i]
return i
def sort(low, high):
if low < high:
p = partition(low, high)
sort(low, p - 1)
sort(p + 1, high)
sort(0, len(nums) - 1)
return nums
6. Non-comparison Sorting
Counting sort
Counting sort works when values are integers in a small known range. It counts occurrences and reconstructs the sorted
list.
Python Interview Notes Page 3
def counting_sort(nums):
if not nums:
return []
min_val = min(nums)
max_val = max(nums)
counts = [0] * (max_val - min_val + 1)
for n in nums:
counts[n - min_val] += 1
result = []
for i, count in enumerate(counts):
value = i + min_val
[Link]([value] * count)
return result
7. Interview Problems Using Sorting
Check if two strings are anagrams (Easy)
Idea: Sort both strings and compare.
def are_anagrams(a, b):
return sorted(a) == sorted(b)
Interview notes: A dictionary frequency count is often better for O(n), but sorted() is very simple.
Find kth largest element (Medium)
Idea: Sort descending and return index k - 1. Then discuss heap or quickselect as improvements.
def kth_largest(nums, k):
[Link](reverse=True)
return nums[k - 1]
Merge intervals (Medium)
Idea: Sort intervals by start time, then merge overlapping intervals.
def merge_intervals(intervals):
if not intervals:
return []
[Link](key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last = merged[-1]
if start <= last[1]:
last[1] = max(last[1], end)
else:
[Link]([start, end])
return merged
Sort colors / Dutch national flag (Medium)
Idea: Sort a list containing only 0, 1, and 2 using three pointers.
def sort_colors(nums):
low = 0
mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
Python Interview Notes Page 4
Top k frequent elements (Medium/Harder)
Idea: Count frequencies, then sort by frequency.
from collections import Counter
def top_k_frequent(nums, k):
freq = Counter(nums)
items = list([Link]())
[Link](key=lambda x: x[1], reverse=True)
return [value for value, count in items[:k]]
8. Tips for Explaining Sorting in Interviews
●
Start with the main idea before writing code.
●
Say whether the algorithm sorts in place or returns a new list.
●
Mention time and space complexity.
●
Mention whether it is stable if relevant.
●
Use Python built-in sort for production code unless asked to implement manually.
●
For nearly sorted data, insertion sort can perform very well.
●
For guaranteed O(n log n), merge sort is easier to reason about than quick sort.
●
For small integer ranges, counting sort can beat comparison sorting.
9. Practice Order
1 Use sort() and sorted() with key functions.
2 Bubble sort.
3 Selection sort.
4 Insertion sort.
5 Merge two sorted lists.
6 Merge sort.
7 Quick sort.
8 Counting sort.
9 Check anagrams using sorting.
10 Kth largest element.
11 Merge intervals.
12 Sort colors.
13 Top k frequent elements.
Python Interview Notes Page 5