Sorting and Searching Algorithms
A short practical guide for students: when to use each algorithm, key ideas, Python
patterns, and practice questions.
1. How to Choose an Algorithm
An algorithm is a step-by-step method for solving a problem. For sorting and searching, the main
questions are: how much data, is it already sorted, do you need speed, and do you need stable
ordering?
• Small data: simple algorithms are often fine.
• Large data: use O(n log n) sorting and O(log n) searching when possible.
• Already sorted data: binary search becomes very powerful.
• Repeated searches: sort once, then search many times.
Term Meaning Quick example
Time complexity How running time grows O(n), O(n log n), O(n^2)
Space complexity Extra memory needed Merge sort uses extra arrays
Stable sort Equal items keep original order Useful when sorting records by multiple fields
In-place Uses little extra memory Selection sort, quicksort variants
2. Searching Algorithms
Algorithm Use when Time Idea
Linear search Data is unsorted or small O(n) Check items one by one
Binary search Data is sorted O(log n) Repeatedly cut the search range
in half
Hash lookup You need very fast exact lookup Average O(1) Use a hash table / dictionary
Two pointers Sorted array or pair problems O(n) Move left and right pointers
inward
Binary search pattern
def binary_search(a, target):
left, right = 0, len(a) - 1
while left <= right:
mid = (left + right) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Common mistake: binary search only works correctly when the data is sorted using the same order you are
searching with.
3. Simple Sorting Algorithms
Computer Algorithms - Quick Guide Page 1
These are useful for learning, small inputs, or special cases. They are usually not the best choice for
very large lists.
Algorithm Time Stable? Main idea When useful
Bubble sort O(n^2) Yes Swap neighboring items Teaching only
Selection sort O(n^2) No Repeatedly select smallest Very low memory
item
Insertion sort O(n^2), fast if nearly Yes Insert each item into correct Small or nearly
sorted place sorted data
Insertion sort pattern
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
4. Faster Sorting Algorithms
Algorithm Average time Worst time Stable? Notes
Merge sort O(n log n) O(n log n) Yes Reliable, but uses extra memory
Quick sort O(n log n) O(n^2) Usually no Very fast in practice with good pivot
choice
Heap sort O(n log n) O(n log n) No Good worst-case time, in-place
Timsort O(n log n), fast on O(n log n) Yes Used by Python sorted() and
real data [Link]()
Merge sort idea
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
return merge(left, right) # merge two sorted lists
Practical rule: in Python, use sorted() unless you are studying algorithms or need to implement a special
case.
5. Practice Questions
• Which algorithm would you use to find a student ID in a sorted list? Why?
• Why is bubble sort usually a poor choice for large data?
• Sort this list using insertion sort: [5, 2, 4, 1, 3]. Show each pass.
• A website must search usernames quickly. Which data structure is suitable?
• Explain the difference between O(n), O(log n), and O(n log n) in simple words.
Answer hints
• Sorted list search: binary search.
Computer Algorithms - Quick Guide Page 2
• Bubble sort grows too slowly: O(n^2).
• Insertion sort moves each item left until it is in the correct position.
• Hash table / dictionary is good for exact username lookup.
• O(log n) grows very slowly; O(n) grows directly with data; O(n log n) is common for efficient sorting.
Computer Algorithms - Quick Guide Page 3