Sorting Algorithms
Bubble, Merge, and Quick Sort — how computers put things in order, and at what cost.
Bubble Sort (Simple but Slow)
Bubble Sort repeatedly compares adjacent elements and swaps them if they're in the wrong order, 'bubbling' the largest element to the end each pass. It's easy to understand but runs in O(n²) — too slow for large datasets.
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);Merge Sort (Divide and Conquer)
Merge Sort splits the array into halves, recursively sorts each half, then merges the sorted halves back together. It always runs in O(n log n), making it reliable for large datasets, though it uses extra memory for merging.
Quick Sort (Fast in Practice)
Quick Sort picks a 'pivot' element, partitions the array so smaller elements go left and larger go right, then recursively sorts each side. Average case O(n log n), but worst case O(n²) if the pivot is chosen poorly (e.g. already sorted data).
🌍 Real-World Use
When you sort a spreadsheet column or a shopping site sorts products by price, a variation of Merge Sort or Quick Sort typically runs behind the scenes — most language standard libraries (like Java's Arrays.sort or Python's sorted()) use a hybrid of these.
💡 Pro Tip
You don't need to memorize every sorting algorithm's code by heart, but you MUST know their time complexities and when to use which — this is one of the most frequently asked theory questions in interviews.
🧪 Quick Self-Test
Check what you just learned — no pressure, just practice.
1. What is the average time complexity of Merge Sort?
2. Which sort can degrade to O(n²) with a poor pivot choice?