
AI Computing
Sorting Algorithms
Sorting is organizing data in ascending or descending order. Essential for searching, data analysis, and optimization.
Why Sorting Matters
- Search Efficiency: Binary search requires sorted data
- Data Analysis: Find median, percentiles, outliers
- Optimization: Many algorithms need sorted input
- User Experience: Display sorted results
Algorithm 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 |
Simple Sorting Algorithms
1. Bubble Sort
How it works: Repeatedly swap adjacent elements if in wrong order.
codedef 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: # Optimization break return arr # Example arr = [64, 34, 25, 12, 22] print(bubble_sort(arr)) # [12, 22, 25, 34, 64]
Time: O(n²) | Space: O(1) | Stable: Yes Use: Small datasets, nearly sorted data, educational
2. Selection Sort
How it works: Find minimum element, swap with first position, repeat.
codedef selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr
Time: O(n²) | Space: O(1) | Stable: No Use: Small datasets, memory limited
3. Insertion Sort
How it works: Build sorted array one element at a time.
codedef insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr
Time: O(n²) average, O(n) best | Space: O(1) | Stable: Yes Use: Small datasets, nearly sorted, online sorting
Efficient Sorting Algorithms
4. Merge Sort
How it works: Divide array, sort halves, merge them.
codedef 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) always | Space: O(n) | Stable: Yes Use: Large datasets, linked lists, external sorting
Advantages: ✅ Guaranteed O(n log n) ✅ Stable ✅ Good for linked lists
Disadvantages: ❌ Extra space O(n) ❌ Slower than quicksort in practice
5. Quick Sort
How it works: Pick pivot, partition array, recursively sort.
codedef 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) # In-place version def quick_sort_inplace(arr, low, high): if low < high: pi = partition(arr, low, high) quick_sort_inplace(arr, low, pi-1) quick_sort_inplace(arr, pi+1, high) def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[high] = arr[high], arr[i+1] return i + 1
Time: O(n log n) average, O(n²) worst | Space: O(log n) | Stable: No Use: General purpose, in-place sorting
Pivot Selection Strategies:
- First/last element (bad for sorted data)
- Middle element
- Random element (good average)
- Median-of-three (best)
6. Heap Sort
How it works: Build max heap, repeatedly extract maximum.
codedef heap_sort(arr): n = len(arr) # Build max heap for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from heap for i in range(n-1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
Time: O(n log n) always | Space: O(1) | Stable: No Use: Memory constrained, guaranteed O(n log n)
Choosing the Right Algorithm
Small data (< 50 elements): Insertion Sort General purpose: Quick Sort Guaranteed O(n log n): Merge Sort or Heap Sort Nearly sorted: Insertion Sort Stable sort needed: Merge Sort Memory limited: Heap Sort or Quick Sort External sorting: Merge Sort
Special Sorting Algorithms
Counting Sort
For integers in limited range.
codedef counting_sort(arr): max_val = max(arr) count = [0] * (max_val + 1) for num in arr: count[num] += 1 result = [] for i, c in enumerate(count): result.extend([i] * c) return result
Time: O(n + k) where k = range | Space: O(k)
Radix Sort
Sort by individual digits.
codedef radix_sort(arr): max_val = max(arr) exp = 1 while max_val // exp > 0: counting_sort_by_digit(arr, exp) exp *= 10 return arr
Time: O(d × n) where d = digits | Space: O(n)
Real-World Applications
- E-commerce: Sort by price, rating, date
- Social Media: Sort posts by time, likes
- Databases: ORDER BY queries
- Search Engines: Rank results
- File Systems: Sort files by name, size, date
- Data Analysis: Find top K elements
Practice Problems
- Sort array of 0s, 1s, 2s (Dutch National Flag)
- Merge K sorted arrays
- Sort array by frequency
- Sort colors (3-way partitioning)
- Find Kth largest element
- Sort linked list
- Custom comparator sorting