Detailed Sorting Algorithm Notes (Strivers A2Z DSA
Course)
This document provides structured notes on fundamental sorting algorithms, covering their
concept, time complexity, and implementation details, as discussed in the videos.
I. Comparison-Based O(N^2) Sorting Algorithms
These algorithms are generally not used for large datasets but are foundational and offer O(N)
performance in best-case scenarios (Insertion/Bubble Sort) or O(N^2) stability (Selection
Sort).
1. Selection Sort
● Concept: The algorithm selects the minimum element from the unsorted subarray and
swaps it with the element at the beginning of the unsorted subarray.
● Key Idea: Select minimums and swap them into the correct position.
● Process:
○ Start an outer loop from i=0 to N-2. This i marks the start of the unsorted array.
○ Inside, find the index of the minimum element (min\_idx) in the subarray from
i to N-1.
○ Swap the element at arr[i] with the element at arr[min\_idx].
○ The elements from index 0 to i are now sorted.
● Time Complexity:
○ Best Case: O(N^2)
○ Average Case: O(N^2)
○ Worst Case: O(N^2)
● Stability: Unstable. The comparison count is always the same, regardless of the initial
array state.
C++ Core Function
void selectionSort(std::vector<int>& arr, int n) {
// Outer loop traverses the array to place elements one by one
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
// Inner loop finds the minimum element in the remaining unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap the found minimum element with the first element of the unsorted part
if (min_idx != i) {
std::swap(arr[i], arr[min_idx]);
}
}
}
2. Bubble Sort
● Concept: Repeatedly compares adjacent elements and swaps them if they are in the
wrong order. This process "bubbles" the largest element to its correct position at the end
of the array in each pass.
● Key Idea: Adjacent swapping to push the maximum element to the last unsorted index.
● Process:
○ Outer loop runs from i=N-1 down to 1 (number of passes required).
○ Inner loop runs from j=0 to i-1.
○ If arr[j] > arr[j+1], swap them.
● Optimization (Best Case): An optimization can be introduced using a didSwap flag. If
a pass completes without any swaps, the array is already sorted, and the algorithm
breaks the outer loop.
● Time Complexity:
○ Best Case (Optimized): O(N) (Array is already sorted)
○ Average Case: O(N^2)
○ Worst Case (Reversed Array): O(N^2)
C++ Core Function
void bubbleSort(std::vector<int>& arr, int n) {
for (int i = 0; i < n - 1; i++) {
bool didSwap = false; // Optimization flag
// n - 1 - i is the last index to check in the unsorted part
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
didSwap = true;
}
}
// If no two elements were swapped, array is sorted
if (didSwap == false) {
break;
}
}
}
3. Insertion Sort
● Concept: Takes an element and inserts it into its correct position within the already
sorted portion of the array to its left.
● Key Idea: Inserting an element into an already sorted subarray.
● Process:
○ Outer loop runs from i=1 to N-1. The element at arr[i] is the "key" to be
inserted.
○ Inner loop (usually a while loop) compares the key with elements to its left
(j-1).
○ If arr[j-1] is greater than the key, shift arr[j-1] one position to the right
(arr[j] = arr[j-1]).
○ This shifting continues until the correct position for the key is found, and the key
is inserted there.
● Time Complexity:
○ Best Case (Sorted Array): O(N) (Only the outer loop runs)
○ Average Case: O(N^2)
○ Worst Case (Reversed Array): O(N^2)
C++ Core Function
void insertionSort(std::vector<int>& arr, int n) {
// Start from the second element
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements of arr[0..i-1] that are greater than key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Insert the key into its correct position
arr[j + 1] = key;
}
}
II. Comparison-Based O(N log N) Sorting Algorithms
These algorithms are highly efficient for large datasets due to their logarithmic complexity in
time.
4. Merge Sort
● Concept: A Divide and Conquer algorithm that recursively splits the array into two
halves until single-element arrays are obtained. It then merges these single-element
arrays in a sorted manner.
● Key Idea: Divide the problem, conquer (solve the subproblems), and combine (merge
the sorted results).
● Algorithm Flow:
○ Divide: The array is recursively split into left (low to mid) and right (mid+1 to
high) subarrays.
○ Conquer (Recursion): This step continues until the base case is reached (low
== high, a single element).
○ Merge: A helper function combines two adjacent sorted subarrays into a single
sorted array. This requires an auxiliary temporary array to store the merged
results before copying them back to the original array.
● Time Complexity:
○ Best/Average/Worst Case: O(N log N) (The complexity is always consistent).
● Space Complexity: O(N) (Auxiliary space for the temporary array used in the merge
step).
● Stability: Stable. The relative order of equal elements is preserved during the merge
step.
C++ Core Functions
// Helper function to merge two sorted sub-arrays
void merge(std::vector<int>& arr, int low, int mid, int high) {
std::vector<int> temp;
int left = low;
int right = mid + 1;
// Compare and add elements from both halves
while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp.push_back(arr[left++]);
} else {
temp.push_back(arr[right++]);
}
}
// Copy remaining elements
while (left <= mid) temp.push_back(arr[left++]);
while (right <= high) temp.push_back(arr[right++]);
// Copy sorted elements back to the original array
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
}
// Main recursive function
void mergeSort(std::vector<int>& arr, int low, int high) {
if (low >= high) return; // Base case
int mid = low + (high - low) / 2;
// Divide (Recurse)
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
// Combine (Merge)
merge(arr, low, mid, high);
}
5. Quick Sort
● Concept: Another Divide and Conquer algorithm. It selects a 'pivot' element and
partitions the array around it, such that all elements smaller than the pivot come before
it, and all greater elements come after it.
● Key Idea: The pivot is placed in its correct final sorted position during the
partitioning step.
● Lomuto Partition Scheme (Used in the video):
○ Choose the last element as the pivot.
○ Initialize two pointers: i (index of the smaller element, starts at low-1) and j
(iterator, starts at low).
○ Iterate j from low to high-1.
○ If arr[j] is less than or equal to the pivot, increment i and swap arr[i] with
arr[j].
○ Finally, swap the pivot (arr[high]) with arr[i+1]. i+1 is the pivot's correct
position.
● Algorithm Flow:
○ Choose a pivot and run the Partition function.
○ The Partition function returns the index of the pivot's final position.
○ Recursively call Quick Sort on the left subarray (elements before the pivot).
○ Recursively call Quick Sort on the right subarray (elements after the pivot).
● Time Complexity:
○ Average Case: O(N log N)
○ Worst Case: O(N^2) (When the pivot is always the smallest or largest element).
○ Best Case: O(N log N)
● Space Complexity: O(log N) (Due to the recursion stack, logarithmic in the average
case).
● Stability: Unstable (Swaps can disrupt the relative order of equal elements).
C++ Core Functions
// Helper function to partition the array around the pivot (Lomuto Scheme)
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // Last element as pivot
int i = (low - 1);
// Iterate through elements, comparing to pivot
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
// Place pivot in its correct final position
std::swap(arr[i + 1], arr[high]);
return (i + 1); // Return the partitioning index
}
// Main recursive function
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partitioning index
// Recurse on the sub-arrays
quickSort(arr, low, pi - 1); // Left side
quickSort(arr, pi + 1, high); // Right side
}
}