Sorting is a fundamental operation in computer science and Understanding the basic sorting algorithms is essential for both interviews and real-world programming tasks. I am sharing the notes that I have taken in my learning curve.
1. Selection Sort
Selection Sort repeatedly finds the minimum element from the unsorted part and puts it at the beginning.
Steps:
- Loop through the array.
- For each index, find the smallest element in the rest of the array.
- Swap it with the current index.
Time Complexity: O(n²)
Example:
[29, 10, 14, 37, 13]
→ [10, 29, 14, 37, 13]
→ [10, 13, 14, 37, 29]
→ [10, 13, 14, 37, 29]
→ [10, 13, 14, 29, 37]
2. Insertion Sort
Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position.
Steps:
- Start from index 1.
- Compare current element with the left-side elements.
- Shift elements to the right and insert at the correct position.
Time Complexity: O(n²)
Example:
[8, 4, 1, 3]
→ [4, 8, 1, 3]
→ [1, 4, 8, 3]
→ [1, 3, 4, 8]
3. Bubble Sort
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Steps:
- Compare each pair of adjacent items.
- Swap them if needed.
- Repeat until no swaps are needed.
Time Complexity: O(n²)
Example:
[5, 3, 8, 4]
→ [3, 5, 4, 8]
→ [3, 4, 5, 8]
4. Quick Sort
Quick Sort is a divide-and-conquer algorithm. It selects a pivot, partitions the array, and recursively sorts the subarrays.
Steps:
- Choose a pivot.
- Partition the array into left (less than pivot) and right (greater).
- Recursively apply the same logic.
Time Complexity:
Average: O(n log n)
Worst: O(n²) (when poorly partitioned)
Example:
[9, 3, 7, 1]
Pivot = 3 → [1] + [3] + [9, 7]
→ [1, 3] + quickSort([9, 7]) → [1, 3, 7, 9]
5. Merge Sort
Merge Sort is a stable divide-and-conquer algorithm that divides the array in half, sorts each half, and merges them.
Steps:
- Divide the array into halves.
- Sort each half recursively.
- Merge the sorted halves.
Time Complexity: O(n log n)
Example:
[6, 2, 4, 1]
→ [6, 2], [4, 1]
→ [2, 6], [1, 4]
→ merge → [1, 2, 4, 6]