1.
Search in Rotated Sorted Array
Problem: Find a key in a sorted array that has been rotated.
1 int searchRotated (vector <int >& nums , int key) {
2 int low = 0, high = [Link] () - 1;
3
4 while (low <= high) {
5 int mid = (low + high) / 2;
6
7 if (nums[mid] == key) return mid;
8
9 // Check if left half is sorted
10 if (nums[low] <= nums[mid ]) {
11 if (nums[low] <= key && key < nums[mid ])
12 high = mid - 1;
13 else
14 low = mid + 1;
15 }
16 // Otherwise , right half must be sorted
17 else {
18 if (nums[mid] < key && key <= nums[high ])
19 low = mid + 1;
20 else
21 high = mid - 1;
22 }
23 }
24 return -1;
25 }
Complexity: Time: O(log n) | Space: O(1)
2. Merge Sort (Recursive)
Idea: Divide array into halves, sort them, then merge.
1 void merge(vector <int >& a, int l, int m, int r) {
2 int n1 = m - l + 1, n2 = r - m;
3 vector <int > L(n1), R(n2);
4 for (int i=0; i<n1; i++) L[i] = a[l + i];
5 for (int j=0; j<n2; j++) R[j] = a[m + 1 + j];
6
7 int i = 0, j = 0, k = l;
8 while (i < n1 && j < n2)
9 a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
10 while (i < n1) a[k++] = L[i++];
11 while (j < n2) a[k++] = R[j++];
12 }
13
14 void mergeSort (vector <int >& a, int l, int r) {
15 if (l >= r) return ;
16 int m = l + (r - l) / 2;
17 mergeSort (a, l, m);
18 mergeSort (a, m + 1, r);
19 merge(a, l, m, r);
20 }
Complexity: Time: O(n log n) | Space: O(n)
3. Merge Sort (Iterative)
Idea: Bottom-up approach. Sort subarrays of size 1, 2, 4... useful when recursion depth is a concern.
1 // Requires the 'merge ' function from the previous box
2
3 void mergeSortIterative (vector <int >& a) {
4 int n = [Link] ();
5
6 // Double the sub - array size in each pass
7 for (int size = 1; size < n; size *= 2) {
8
9 // Merge subarrays of current 'size '
10 for (int left = 0; left < n - size; left += 2 * size) {
11 int mid = left + size - 1;
12 int right = min(left + 2 * size - 1, n - 1);
13
14 merge(a, left , mid , right);
15 }
16 }
17 }
Key Use: When recursion stack space is limited or expensive (e.g., embedded systems).
4. Quick Sort
Idea: Pick a pivot, partition array (smaller left, larger right), then recursively sort.
1 int partition (vector <int >& a, int low , int high) {
2 int pivot = a[high ];
3 int i = low - 1; // Index of smaller element
4
5 for (int j = low; j < high; j++) {
6 if (a[j] < pivot) {
7 i++;
8 swap(a[i], a[j]);
9 }
10 }
11 swap(a[i + 1], a[high ]);
12 return i + 1;
13 }
14
15 void quickSort (vector <int >& a, int low , int high) {
16 if (low < high) {
17 int p = partition (a, low , high);
18
19 quickSort (a, low , p - 1);
20 quickSort (a, p + 1, high);
21 }
22 }
Complexity: Avg: O(n log n), Worst: O(n2 ). In-place.
5. Min Swaps to Sort (Parity)
Problem: Find minimum swaps to sort an array.
1 int minSwaps (vector <int >& a) {
2 int n = [Link] ();
3 vector <pair <int ,int >> v(n);
4 for (int i = 0; i < n; i++) v[i] = {a[i], i};
5
6 sort([Link] (), [Link] ()); // Sort by value to find correct pos
7 vector <bool > visited (n, false );
8 int swaps = 0;
9
10 for (int i = 0; i < n; i++) {
11 // If visited or already in correct place
12 if ( visited [i] || v[i]. second == i) continue ;
13
14 int cycle_size = 0;
15 int j = i;
16 while (! visited [j]) {
17 visited [j] = true;
18 j = v[j]. second ; // Move to next node in cycle
19 cycle_size ++;
20 }
21 if( cycle_size > 0) swaps += ( cycle_size - 1);
22 }
23 return swaps;
24 }
Theory: Decompose permutation into disjoint cycles.
6. Counting Sort
Idea: Non-comparison sort based on key frequency.
1 void countingSort (vector <int >& a) {
2 if ([Link] ()) return ;
3
4 // 1. Find Range
5 int maxVal = * max_element ([Link] (), [Link] ());
6
7 // 2. Count Frequencies
8 vector <int > count( maxVal + 1, 0);
9 for (int x : a)
10 count[x]++;
11
12 // 3. Reconstruct Array
13 int idx = 0;
14 for (int i = 0; i <= maxVal ; i++) {
15 while (count[i]--) {
16 a[idx ++] = i;
17 }
18 }
19 }
Constraints: Effective only when range of input (k) is not significantly larger than number of ele-
ments (n). Time: O(n + k).