Algorithm Basics — Sorting, Searching, Recursion, Design Principles
Why Algorithm Basics Matter
Algorithms are the recipes that tell computers how to solve problems. Understanding fundamental algorithms — their logic, complexity, and trade-offs — is essential for every software engineer. This knowledge helps you choose the right approach for any problem and write code that scales.
Why this matters for your career:
- Algorithm questions dominate technical interviews at every level
- Understanding algorithm complexity prevents writing slow code
- Sorting and searching are the most common operations in software
- Algorithm design patterns apply to every domain — from databases to AI
Sorting Algorithms
Bubble Sort — O(n²)
Simplest sorting algorithm. Repeatedly swaps adjacent elements if they are in the wrong order.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # Early termination if already sorted
break
return arr
Time: O(n²) average and worst, O(n) best (already sorted) Space: O(1) in-place Use: Educational only — too slow for real data
Merge Sort — O(n log n)
Divide and conquer: split array in half, recursively sort each half, then merge.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Time: O(n log n) all cases Space: O(n) — creates new arrays Use: When stable sorting is needed or worst-case guarantee matters
Quick Sort — O(n log n) average, O(n²) worst
Pick a pivot, partition elements around it, recursively sort each partition.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
Time: O(n log n) average, O(n²) worst (rare with random pivot) Space: O(log n) for recursion stack Use: Default choice for general-purpose sorting (used in most standard libraries)
Sorting Comparison
| Algorithm | Best | Average | Worst | Space | Stable | |-----------|------|---------|-------|-------|--------| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | | 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²) | O(log n) | No | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | | Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | | Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Timsort is Python's default sorting algorithm — a hybrid of merge sort and insertion sort optimized for real-world data.
Searching Algorithms
Linear Search — O(n)
Check each element until found.
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
Use: Unsorted data, small arrays
Binary Search — O(log n)
Repeatedly divide the search interval in half. Requires sorted input.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Recursive version
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
Time: O(log n) Space: O(1) iterative, O(log n) recursive Use: Searching in sorted data — fundamental operation in databases and algorithms
Recursion
Recursion solves a problem by solving smaller instances of the same problem.
Three Laws of Recursion
- A recursive algorithm must have a base case
- A recursive algorithm must change its state and move toward the base case
- A recursive algorithm must call itself, recursively
Classic Examples
# Factorial
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
# Fibonacci
def fibonacci(n):
if n <= 1: # base case
return n
return fibonacci(n - 1) + fibonacci(n - 2) # recursive case
# Note: simple Fibonacci is O(2^n) — use memoization!
def fibonacci_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
Algorithm Design Patterns
| Pattern | Description | Examples | |---------|-------------|--------| | Brute Force | Try all possibilities | Linear search, bubble sort | | Divide and Conquer | Split problem, solve parts, combine | Merge sort, quick sort, binary search | | Greedy | Make locally optimal choice at each step | Dijkstra's algorithm, Huffman coding | | Dynamic Programming | Solve sub-problems once, reuse results | Knapsack, LCS, Fibonacci with memo | | Backtracking | Build solution incrementally, backtrack on failure | N-Queens, Sudoku solver | | Two Pointers | Use two pointers to traverse data | Two-sum for sorted array, palindrome check | | Sliding Window | Maintain a window of elements | Maximum sum subarray, longest substring |
Summary
Fundamental algorithms — sorting, searching, recursion — are the building blocks of all software. Understanding their time and space complexity, strengths, and trade-offs is essential for writing efficient code and succeeding in technical interviews.
Key takeaways:
- Merge Sort: O(n log n), stable, uses O(n) space — guaranteed performance
- Quick Sort: O(n log n) average, O(1) extra space (in-place) — fastest in practice
- Binary Search: O(log n) on sorted data — essential for efficient search
- Recursion requires a base case + movement toward the base case
- Algorithm design patterns: Divide & Conquer, Greedy, DP, Backtracking
- Choose algorithms based on data size, stability requirements, and space constraints
- Profile before optimizing — sometimes O(n²) is fine for small data
What's Next: Coding 101 — Python & JavaScript
The next course covers practical coding fundamentals in Python and JavaScript — variables, data types, control flow, functions, and building your first programs.