Why Sorting Matters and How It Unlocks Other Algorithms in DSA C++ - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sorting and Searching in a Sorted Array

What is the output of the following C++ code that sorts an array and then performs a binary search for the number 7?

DSA C++

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {10, 3, 7, 1, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr + n);
    bool found = binary_search(arr, arr + n, 7);
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl << (found ? "Found" : "Not Found") << endl;
    return 0;
}

A

10 3 7 1 9 
Found

B

1 3 7 9 10 
7

C

1 3 7 9 10 
Not Found

D

1 3 7 9 10 
Found

💡 Hint

Remember that std::sort sorts the array in ascending order and binary_search requires a sorted array.

The array is sorted to 1 3 7 9 10. Then binary_search finds 7 in the sorted array, so it prints 'Found'.

🧠 Conceptual

intermediate

Why Sorting Helps in Finding Duplicates

Why does sorting an array first make it easier to find duplicates?

A Because sorting changes the values of elements to unique ones.

B Because sorting removes duplicates automatically.

C Because after sorting, duplicates will be next to each other, so we only need to check adjacent elements.

D Because sorting splits the array into two halves, making duplicates impossible.

💡 Hint

Think about how duplicates appear in a sorted list.

Sorting arranges equal elements next to each other, so checking neighbors is enough to find duplicates efficiently.

🔧 Debug

advanced

Identify the Error in Merge Sort Implementation

What error does the following C++ merge sort code produce when run?

DSA C++

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for(int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(int j = 0; j < n2; j++)
        R[j] = arr[m + j];
    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

A The code compiles but outputs an unsorted array.

B Compilation error because variable-length arrays are not allowed in standard C++.

C Runtime error due to accessing out-of-bounds in array R.

D Logical error: merge function merges incorrectly causing infinite recursion.

💡 Hint

Check the declarations of arrays L and R inside merge function.

Standard C++ does not allow variable-length arrays like int L[n1]; This causes compilation error.

🚀 Application

advanced

Using Sorting to Find the Intersection of Two Arrays

Given two unsorted arrays, which approach correctly finds their intersection using sorting?

A Sort both arrays, then use two pointers to find common elements in O(n log n + m log m) time.

B Sort only the first array, then for each element in second array, do a linear search in the first array.

C Sort the second array, then use binary search for each element of the first array in the second array.

D Sort both arrays, then merge them into one sorted array to get the intersection.

💡 Hint

Think about how two sorted arrays can be traversed efficiently.

Sorting both arrays allows using two pointers to find common elements efficiently without repeated searching.

❓ Predict Output

expert

Output of Counting Inversions Using Merge Sort

What is the output of the following C++ code that counts the number of inversions in an array using merge sort?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

long long merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2);
    for(int i = 0; i < n1; i++) L[i] = arr[l + i];
    for(int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    long long inv_count = 0;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
            inv_count += (n1 - i);
        }
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
    return inv_count;
}

long long mergeSort(vector<int>& arr, int l, int r) {
    long long inv_count = 0;
    if(l < r) {
        int m = l + (r - l) / 2;
        inv_count += mergeSort(arr, l, m);
        inv_count += mergeSort(arr, m + 1, r);
        inv_count += merge(arr, l, m, r);
    }
    return inv_count;
}

int main() {
    vector<int> arr = {2, 4, 1, 3, 5};
    long long result = mergeSort(arr, 0, arr.size() - 1);
    cout << result << endl;
    return 0;
}

A

3

B

4

C

2

D

5

💡 Hint

Count pairs (i, j) where i < j and arr[i] > arr[j].

The inversions are (2,1), (4,1), (4,3) totaling 3 inversions.