Intro to Sorting Algorithms
What is Sorting?
Sorting is the process of arranging data in a specific order — either ascending or descending. It is one of the most fundamental operations in computer science, forming the foundation for efficient searching, data processing, and algorithm design.
Example — ascending sort:
Types of Sorting Algorithms
1. Comparison-Based Sorting
Sort by comparing elements with each other. Lower bound: O(n log n)
- Bubble Sort — repeatedly swaps adjacent elements
- Insertion Sort — inserts each element into its correct position
- Selection Sort — selects the minimum and places it at the front
- Merge Sort — divide and conquer, always O(n log n)
- Quick Sort — pivot-based partitioning, O(n log n) average
2. Non-Comparison Based Sorting
Sort without direct comparisons — can achieve O(n) time
- Counting Sort — count occurrences, O(n + k)
- Radix Sort — sort digit by digit, O(nk)
3. Hybrid Algorithms
Combine strategies for optimal real-world performance
- Timsort — Merge Sort + Insertion Sort (Python, Java built-in)
- Introsort — Quick Sort + Heap Sort (C++ STL built-in)
Key Concept: In-Place Sorting
A sorting algorithm is in-place if it sorts using O(1) extra space — it modifies the original array without allocating an extra copy.
✅ In-place: Bubble Sort, Selection Sort, Insertion Sort
❌ NOT in-place: Merge Sort — requires O(n) auxiliary space for temp arrays
# Bubble Sort -- in-place, no extra array needed arr = [3, 1, 2] # [1, 3, 2] --> [1, 2, 3] Only swaps within arr itself
Key Concept: Stable Sorting
A sorting algorithm is stable if elements with equal keys maintain their original relative order after sorting.
# Example: Sort students by marks Original: [(Alice, 80), (Bob, 90), (Charlie, 80)] Stable sort by marks: --> [(Alice, 80), (Charlie, 80), (Bob, 90)] Alice still before Charlie Unstable sort might give: --> [(Charlie, 80), (Alice, 80), (Bob, 90)] Relative order changed!
Algorithm Comparison Table
| Algorithm | Stable? | In-Place? | Best | Average | Worst |
|---|---|---|---|---|---|
| Bubble Sort | ✅ Yes | ✅ Yes | O(n) | O(n²) | O(n²) |
| Insertion Sort | ✅ Yes | ✅ Yes | O(n) | O(n²) | O(n²) |
| Selection Sort | ❌ No | ✅ Yes | O(n²) | O(n²) | O(n²) |
| Merge Sort | ✅ Yes | ❌ No | O(n log n) | O(n log n) | O(n log n) |
| Quick Sort | ❌ No | ✅ Yes | O(n log n) | O(n log n) | O(n²) |