1. Introduction to Sorting
- Sorting = Arranging data in a particular order (ascending or descending).
- Essential for search efficiency, data analysis, and algorithm optimization.
- Internal Sort – Data fits in main memory.
- External Sort – Data too large, stored in external storage (disk).
2. Common Sorting Algorithms
1. Insertion Sort
- Build sorted list one element at a time.
- Compare current element with sorted portion and insert at correct position.
- Time Complexity: O(n²), Best Case: O(n).
- Stable – maintains relative order of equal elements.
2. Selection Sort
- Select minimum (or maximum) element and place in correct position.
- Time Complexity: O(n²).
- Unstable – may change order of equal elements.
3. Bubble Sort
- Repeatedly swap adjacent elements if out of order.
- Continue until no swaps needed.
- Time Complexity: O(n²).
- Stable.
4. Quick Sort
- Divide and Conquer: Select pivot, partition array, recursively sort partitions.
- Time Complexity: Average O(n log n), Worst O(n²).
- Unstable.
5. Merge Sort
- Divide array into halves, recursively sort, merge sorted halves.
- Time Complexity: O(n log n).
- Stable.
6. Heap Sort
- Build max-heap and repeatedly extract maximum.
- Time Complexity: O(n log n).
- Unstable.
- Can implement priority queue.
7. Other Sorts
- Shell Sort – Improved insertion sort using gaps.
- Radix Sort – Non-comparative, uses digits of numbers.
- Binary Sort – Uses binary search for insertion position.
3. Efficiency of Sorting
| Algorithm | Time Complexity (Best) | Average | Worst | Stable? |
| Insertion | O(n) | O(n²) | O(n²) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | No |
| Bubble | O(n) | O(n²) | O(n²) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | Yes |
| Heap | O(n log n) | O(n log n) | O(n log n) | No |
4. Key Concepts
- Stable Sort – Maintains relative order of equal elements.
- In-place Sort – Requires minimal extra memory (e.g., quick sort, bubble).
- Out-of-place Sort – Needs extra memory (e.g., merge sort).
- Divide and Conquer – Break problem into smaller subproblems (merge, quick).
✅ Key Takeaways – Unit 8
- Sorting arranges data for efficient processing.
- Internal vs external sort depends on memory size.
- Algorithms differ in time, stability, and memory usage.
- Important for searching, database operations, and optimization.
- Quick, Merge, and Heap sorts are preferred for large datasets.
