Sort in C++: Algorithms, Methods & Code Examples

The std::sort() function in C++ is a powerful and efficient sorting tool provided by the Standard Template Library (STL). It is based on Introsort, a hybrid sorting algorithm that switches between Quick Sort, Heap Sort, and Insertion Sort to achieve optimal performance. This makes std::sort() one of the fastest and most commonly used ways to sort in C++

Syntax Of C++ Sort Function (sort())

// Default sorting (Ascending order)
void sort(RandomAccessIterator first, RandomAccessIterator last);

// Sorting with a custom comparator function
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Parameters

• First: An iterator pointing to the start of the range to be sorted.
• Last: An iterator pointing to the end of the range (one position past the last element).
• Comp (optional): A custom comparator function that determines the sorting order.

The std::sort function in C++ is a function template designed for maximum flexibility and efficiency. To use the sort function properly, one must be familiar with the parameters it takes and the information it returns for a number of different situations.

Parameters

std::sort has two main forms:

// Default sorting (ascending order) void sort(RandomAccessIterator first, RandomAccessIterator last); 
// Sorting with a custom comparator void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• first: An iterator (or pointer) pointing to the beginning of the range to be sorted.
  For arrays, this is typically the array name (e.g., arr). For containers like std::vector, use vec.begin().
• last: An iterator (or pointer) pointing just past the end of the range to be sorted.
  For arrays, this is arr + n (where n is the array size). For containers, use vec.end().
• comp (optional): A comparator function, function pointer, or function object (functor) that determines the sorting order.
  If omitted, std::sort uses std::less<T>() (ascending order).
  
  • For descending order, use std::greater<type>().
  • For custom ordering, provide your own function, functor, or lambda.

Comparator Requirements

The comparator must enforce a strict weak ordering.
It should accept two arguments and return true if the first should go before the second.

Examples:

• Using a function pointer:

bool compare(int a, int b) 
{ 
return a > b; 
} 
std::sort(arr, arr + n, compare);

• Using a functor (function object):

struct {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) const {
        return a.second < b.second; // sort by second element
    }
} sortbysec;

std::sort(vec.begin(), vec.end(), sortbysec);

• Using a lambda expression:

std::sort(vec.begin(), vec.end(),
          [](int a, int b) {
              return a > b;  // sort in descending order
          });

Special Parameters (C++17+)

With C++17 and later, you can use an execution policy as the first argument to enable parallel sorting:

#include <execution>

std::sort(std::execution::par,
          vec.begin(),
          vec.end());

• std::execution::par tells the algorithm to use parallel execution (multi-threaded sorting), improving performance on large datasets.

Return Value

std::sort does not return a value.
It sorts the elements in-place, directly modifying the provided range.

How to Interpret the Output

After calling std::sort, the elements in the specified range are reordered according to the chosen comparator. No new container or array is created—the original data is sorted in place.
Always check that your comparator is correct and that your iterators define a valid range to avoid undefined behavior.

Summary Table

<style>
  .table-div {
    width: 100%;
    overflow-x: auto;
    margin: 20px 0;
  }
  table {
    width: 100%;
    border-collapse: collapse;
    font-family: 'Segoe UI', sans-serif;
    font-size: 16px;
  }
  th, td {
    border: 1px solid #ddd;
    padding: 12px 15px;
    vertical-align: top;
    text-align: left;
  }
  th {
    background-color: #004aad;
    color: #fff;
    text-transform: uppercase;
    font-weight: 600;
  }
  tr:nth-child(even) {
    background-color: #f9f9f9;
  }
  tr:hover {
    background-color: #eef5ff;
    transition: 0.3s;
  }
  caption {
    caption-side: top;
    font-size: 18px;
    font-weight: 600;
    margin-bottom: 8px;
    color: #333;
    text-align: left;
  }
</style>

<div class="table-div">
<table>
  <caption>Summary Table</caption>

  <tr>
    <th>Parameter</th>
    <th>Description</th>
  </tr>

  <tr>
    <td>first</td>
    <td>Start of range (iterator or pointer)</td>
  </tr>

  <tr>
    <td>last</td>
    <td>End of range (iterator or pointer, one past last element)</td>
  </tr>

  <tr>
    <td>comp (optional)</td>
    <td>Comparator (function, pointer, functor, or lambda)</td>
  </tr>

  <tr>
    <td>execution policy* (C++17+)</td>
    <td>Parallelization control (std::execution::par)</td>
  </tr>

</table>
</div>

In summary:

Knowing what parameters std::sort accepts and what it returns lets you sort any data type with custom logic, in-place, and even in parallel for modern C++.

Arrays are one of the most commonly used data structures in C++ for storing multiple elements of the same type. Sorting an array is an important operation that helps in searching, organizing, and optimizing data processing. The C++ sort function from the Standard Template Library (STL) efficiently sorts arrays in ascending or descending order with minimal effort.

C++ Sort Array in Ascending Order

#include <iostream>
#include <algorithm>  // For std::sort()

int main() {
    int arr[] = {8, 3, 7, 1, 9, 5};  
    int n = sizeof(arr) / sizeof(arr[0]);  // Calculate array size

    std::sort(arr, arr + n);  // Sort array in ascending order

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";  // Print sorted elements
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the Code

It declares an integer array with items that are not sorted. The array's element count may be found with the help of the sizeof operator. The array is then automatically sorted in ascending order using the C++ sort function. Using Sort in C++, we can efficiently arrange the elements as needed.

After sorting, we use a for loop to iterate through the sorted array and print each element. Compared to simple sorting methods like Bubble Sort or Insertion Sort, std::sort() dramatically lowers the time complexity since it is an efficient sorting algorithm.

Output

Sorted array: 1 3 5 7 8 9

Time and Space Complexity:

• Time Complexity: O(n log n) (on average, due to the internal implementation of QuickSort or IntroSort).
• Space Complexity: O(1) (since sorting is done in place without using extra space).

C++ Sort Array In Descending Order

When an array is sorted descendingly, its elements are arranged from greatest to smallest. Custom sorting measures may be defined using comparison functions with the help of the C++ sort function. We may use std::greater<int>(), which verifies that bigger values appear before smaller ones, to sort an array in descending order.

#include <iostream>
#include <algorithm>  // For std::sort() and std::greater<int>()

int main() {
    int arr[] = {7, 2, 9, 5, 1, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  // Calculate array size

    std::sort(arr, arr + n, std::greater<int>());  // Sort in descending order

    std::cout << "Sorted array in descending order: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";  // Print sorted elements
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

In this program, we declare an integer array with unsorted values. The C++ sort function is then used with std::greater<int>(), which confirms that elements are arranged in descending order. The sorting modifies the array in place.

We will loop through the array's items and output them on the screen in decreasing order after sorting the array's numbers. This is a very efficient way of ordering an array for purposes of ranking information, including score rankings, task prioritization, and arranging information from highest to lowest.

Output

Sorted array in descending order: 9 7 6 5 2 1

Time and Space Complexity:

• Time Complexity: O(n log n) (due to the internal QuickSort/IntroSort mechanism).
• Space Complexity: O(1) (as sorting is performed in place without extra memory).

Summary

• std::sort(arr, arr+n) may be used to sort arrays in either ascending or descending order.
• The function is extremely fast (O(n log n)) and ideal for optimizing searching, ranking, or data organization.
• Useful when working with fixed-size datasets requiring high performance.

Vectors are dynamic arrays in C++ that can grow or shrink in size as needed. Unlike regular arrays, vectors have more flexibility and are highly used in modern programming. Sort in C++ is an essential operation, and vector sort is similar to sorting an array. An effective method for doing this is to use the Standard Template Library's (STL) sort function.

Sorting a Vector in Ascending Order

#include <vector>
#include <iostream>
#include <algorithm>  // For std::sort()

int main() {
    std::vector<int> vec = {7, 2, 9, 1, 5};  

    std::sort(vec.begin(), vec.end());  // Sort vector in ascending order

    std::cout << "Sorted vector: ";
    for (int num : vec) {
        std::cout << num << " ";  // Print sorted elements
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

Here, we declare a vector<int> containing unsorted values. The C++ sort function takes two arguments: vec.begin() (starting position) and vec.end() (ending position) to sort the elements in ascending order. Since C++ vector sort uses dynamic memory, sorting is performed efficiently without needing manual size calculations.

Following sorting, the sorted items are shown by iterating through the vector using a range-based for loop. Because C++ vector sort has built-in methods like push_back() and size() and automatically handles memory allocation, it is superior to arrays.

Output:

Sorted vector: 1 2 5 7 9

Time and Space Complexity

• Time Complexity: O(n log n) (due to the efficient sorting algorithm used internally, generally QuickSort or IntroSort).
• Space Complexity: O(1) (as sorting is done in place without additional memory allocation).

Sorting a Vector in Descending Order

Vectors are dynamic arrays in C++ that allow easy manipulation of elements. Sorting a vector in descending order is useful when arranging data from largest to smallest. The C++ sort function, combined with the std::greater<int>() comparator , is commonly used to sort in C++ efficiently.

#include <iostream>
#include <algorithm>
#include <vector>  // Include vector library

int main() {
    std::vector<int> vec = {7, 2, 9, 1, 5};  // Unsorted vector

    std::sort(vec.begin(), vec.end(), std::greater<int>());  // Sort in descending order

    std::cout << "Sorted vector in descending order: ";
    for (int num : vec) {
        std::cout << num << " ";  // Print sorted vector
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

We define a C++ vector sort containing unsorted elements. The sort function in C++ is used with std::greater<int>() as a comparator so that elements are arranged in descending order. The sorting modifies the vector in place.

We then use a range-based for loop to iterate through the sorted vector and print the elements. This approach provides an efficient way to sort and display data while maintaining code simplicity and readability.

Output

Sorted vector in descending order: 9 7 5 2 1

Time and Space Complexity:

• Time Complexity: O(n log n) (due to the efficient sorting algorithm used internally).
• Space Complexity: O(1) (since sorting is done in place without extra memory usage).

Quick Summary

• Vectors are dynamic arrays and are sorted using std::sort(vec.begin(), vec.end()).
• They offer flexibility, automatic memory management, and better usability than raw arrays.
• Perfect for modern C++ applications where data grows dynamically.

One of the most powerful features of a sort in C++ is its ability to use custom comparison functions. This allows sorting elements based on specific criteria rather than just in ascending order. We can sort elements in descending order by defining a custom comparison function, based on absolute values, string lengths, or any other condition.

Sorting Using Lambda Expressions

Lambda expressions provide a compact and efficient way to define comparison functions directly within the sort function C++. Here is an example showing how to sort a vector in descending order using a lambda function:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {7, 2, 9, 4, 6};

    // Sorting in descending order using a lambda function
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a > b;  // Custom comparison: sort in descending order
    });

    std::cout << "Sorted vector in descending order: ";
    for (int i : vec) {
        std::cout << i << " ";  // Print sorted elements
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

In this program, we use a std::vector<int> to store a set of integers. Instead of the default ascending order, we pass a lambda function to the sort function C++ as a third argument. This lambda function takes two parameters (a and b) and returns true if a is greater than b. 

After sorting, we use a for loop to iterate through the C++ vector sort and print each element. Since the sorting modifies the original vector, no additional space is required for sorting.

Output

Sorted vector in descending order: 9 7 6 4 2

Time and Space Complexity

• Time Complexity: O(n log n) (since std::sort() uses an efficient sorting algorithm).
• Space Complexity: O(1) (in-place sorting without additional memory allocation).

In C++, a functor (function object) is a class or struct that overloads the operator(), which allows objects of that class to be called like functions. Functors are useful for implementing custom comparison logic when sorting data. Unlike regular functions or lambda expressions, functors maintain state and can be reused efficiently.

Sorting Using a Functor in C++

#include <iostream>
#include <algorithm>
#include <vector>

struct CustomCompare {
    bool operator()(int a, int b) const {
        return a > b;  // Sort in descending order
    }
};

int main() {
    std::vector<int> vec = {7, 1, 9, 3, 5};

    std::sort(vec.begin(), vec.end(), CustomCompare());  // Use functor for sorting

    std::cout << "Sorted vector in descending order: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation Of The Code:

In this program, we define a struct CustomCompare that overloads the operator(). This functor returns true when the first argument is greater than the second. We then use the sort function C++ with CustomCompare() as the third argument to apply our custom comparison logic. 

The C++ vector sort is then printed, displaying the elements in descending order. Using functors allows for more flexible and reusable comparison logic, which is useful for complex sorting operations.

Output:

Sorted vector in descending order: 9 7 5 3 1

Time and Space Complexity:

• Time Complexity: O(n log n) (due to the use of QuickSort or IntroSort).
• Space Complexity: O(1) (sorting is done in place without additional memory).

Recap

• Sorting isn’t limited to ascending order; you can sort by absolute values, string length, or any rule you define.
• Lambdas, functors, and custom compare functions allow full control over sorting behavior.
• These are essential for interview problems and organizing complex data structures.

Sorting with Advanced Function Objects (Functors)

C++ lets you build custom function objects, called functors, to control sorting behavior in addition to standard lambdas and comparator functions. Classes or structs known as functors overload operator(), enabling you to contain intricate comparison logic and even save internal information.

Why use functors?

• Reusability: Define once, use in multiple sorts.
• Statefulness: Store configuration or counters inside the functor.
• Performance: Can be inlined by the compiler for efficiency.

Example: Stateful Functor for Custom Sorting

#include <iostream>
#include <algorithm>
#include <vector>

struct ModuloCompare {
    int mod;

    ModuloCompare(int m) : mod(m) {}

    bool operator()(int a, int b) const {
        return (a % mod) < (b % mod);  // compare by modulo value
    }
};

int main() {
    std::vector<int> vec = {13, 7, 2, 19, 5, 11};

    std::sort(vec.begin(), vec.end(), ModuloCompare(5));  // Sort by value modulo 5

    for (int n : vec)
        std::cout << n << " ";
    std::cout << std::endl;

    return 0;
}

Output: 

5 7 2 11 13 19 (sorted by n % 5)

Functors are especially helpful when the comparison logic is reused or needs configuration, such as sorting by a dynamic parameter.

Parallel Execution Policies with std::sort (C++17+)

For large datasets, sorting can become a performance bottleneck. Modern C++ (since C++17) introduces parallel execution policies that allow you to take advantage of multi-core processors with minimal code changes.

How does it work?

The standard library will try to parallelize the sorting process by dividing the work across many threads when std::execution::par is passed as the first parameter to std::sort.

Requirements:

• Available in C++17 and later.
• Works on containers supporting random-access iterators (like std::vector or arrays).
• The comparison function must be thread-safe and not cause side effects.

Example: Sorting with Parallel Execution

#include <iostream>
#include <algorithm>
#include <vector>
#include <execution>   // Required for execution policies

int main() {
    std::vector<int> data = {15, 3, 9, 8, 5, 2, 7, 1, 6, 4};

    std::sort(std::execution::par, data.begin(), data.end());  // Parallel sort

    for (int n : data)
        std::cout << n << " ";
    std::cout << std::endl;

    return 0;
}

Output: 

1 2 3 4 5 6 7 8 9 15

Why use parallel execution?

• Enhancement in performance for big datasets, particularly for computers with many cores.
• Absence of manual threading All parallelization is done behind the scenes by the library.
• Easy upgrade: Sorting mechanism doesn't need to be rewritten; just add std::execution::par.

Caveats:

• Benefits may be outweighed by overhead for small datasets.
• Not supported by all STL implementations or compilers (check your environment).
• Use comparators and containers that are safe for concurrent execution only.

In summary:

• Reusable and adjustable sorting logic is made possible via functors, which are particularly helpful for intricate comparisons.
• C++17 adds std::execution::par to run sorting in parallel, drastically improving performance on large datasets.
• Ideal for high-performance, production-level applications.

When working with user-defined data types in C++, sorting objects of a class is required. Since std::sort() works with fundamental data types by default, we need to specify how objects should be compared. This can be achieved by overloading the < operator inside the class or by providing a custom comparison function. When implementing a Sort in C++ for such objects, providing a well-defined comparison mechanism is essential for correct ordering.

Overloading the < Operator

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

class Person {
public:
    std::string name;
    int age;

    // Constructor to initialize name and age
    Person(const std::string& n, int a) : name(n), age(a) {}

    // Overloading the < operator for sorting based on age
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Aarav", 25},
        {"Meera", 18},
        {"Vikram", 40},
        {"Sanya", 30},
        {"Kabir", 22}
    };

    std::sort(people.begin(), people.end());  // Sorts based on the overloaded < operator

    std::cout << "Sorted people by age:\n";
    for (const Person& person : people) {
        std::cout << "Name: " << person.name << ", Age: " << person.age << "\n";
    }

    return 0;
}

Explanation of the code

In this code, we define a Person class with name and age attributes. The constructor initializes these values. To enable sorting, we overload the < operator so that objects are compared based on the age attribute. 

The std::sort() function then uses this operator to sort function C++ the vector of Person objects. After sorting, a loop iterates through the vector and prints the sorted objects. Since the < operator is overloaded to compare ages, the sorting happens in ascending order of age.

Output

Sorted people by age:
Name: Meera, Age: 18  
Name: Kabir, Age: 22  
Name: Aarav, Age: 25  
Name: Sanya, Age: 30  
Name: Vikram, Age: 40  

Time and Space Complexity:

• Time Complexity: O(n log n) (since sort function C++ is based on QuickSort or IntroSort).
• Space Complexity: O(1) (since sorting is done in place without extra memory usage).

Using a Custom Comparison Function in C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

// Define a Person class
class Person {
public:
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {}  // Constructor
};

// Custom comparator for sorting people by age
struct ComparePeople {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;  // Sort in ascending order of age
    }
};

int main() {
    // Create a list of people
    std::vector<Person> people = {
        {"Esha", 30},
        {"Hrithik", 19},
        {"Isha", 7},
        {"Gauri", 10},
        {"Ishani", 34}
    };

    // Sort the list using custom comparator
    std::sort(people.begin(), people.end(), ComparePeople());

    // Display sorted people
    std::cout << "Sorted people by age:\n";
    for (const Person& person : people) {
        std::cout << "Name: " << person.name << ", Age: " << person.age << "\n";
    }

    return 0;
}

Explanation of the code

A constructor is used to initialize these attributes when objects are created. The ComparePeople structure is then defined, which contains a custom comparison function to sort Person objects by age in ascending order.

The std::sort() function is used with the custom comparator ComparePeople(). Finally, a loop prints the sorted list of people that displays their names and ages in ascending order.

Output

Sorted people by age:
Name: Isha, Age: 7  
Name: Gauri, Age: 10  
Name: Hrithik, Age: 19  
Name: Esha, Age: 30  
Name: Ishani, Age: 34  

Time and Space Complexity:

• Time Complexity: O(n log n) since QuickSort or IntroSort are usually used by std::sort().
• Space Complexity: O(1) since sorting is done in-place without using more memory.

Summary

• To sort objects (like Person), define comparison rules: overload < or provide a custom comparator.
• std::sort() uses these rules to order objects by age, name, or any property
• This is crucial for real-world development where data is object-based.

Except for using the built-in std::sort() function, C++ allows programmers to implement custom sorting algorithms. These algorithms help in understanding how sorting works at a more in-depth level and can be optimized for specific use cases. When learning how to sort in C++, exploring different sorting techniques can provide valuable insights into algorithm efficiency and design.

Bubble Sort Implementation in C++

When nearby items are in the incorrect order, the Bubble Sort algorithm continually compares them and switches them.

#include <iostream>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {  
        for (int j = 0; j < n - i - 1; ++j) {  
            if (arr[j] > arr[j + 1]) {  
                std::swap(arr[j], arr[j + 1]);  // Swap if elements are in the wrong order
            }
        }
    }
}

int main() {
    int arr[] = {6, 2, 8, 4, 10, 1};  
    int n = sizeof(arr) / sizeof(arr[0]);  

    bubbleSort(arr, n);  // Call Bubble Sort function

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";  // Print sorted array
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

We define the bubbleSort() function, which takes an array and its size as arguments. The algorithm iterates through the array multiple times, comparing adjacent elements and swapping them if needed. With each iteration, the largest unsorted element moves to its correct position at the end.

The process continues until the array is completely sorted. The main function initializes an unsorted array, calls bubbleSort(), and then prints the sorted result. However, Bubble Sort is easy to implement.

Output

Sorted array: 1 2 4 6 8 10

Time and Space Complexity:

• Time Complexity: O(n²) (due to the nested loops, making it inefficient for large inputs).
• Space Complexity: O(1) (since it sorts the array in place without using extra memory).

Insertion Sort in C++

Insertion Sort is a basic yet efficient sorting algorithm which functions similarly to how we arrange playing cards in our hands. By selecting each element and positioning it correctly among the previously sorted items, it constructs the sorted array one element at a time.

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];  // Store the current element
        int j = i - 1;

        // Shift elements of the sorted part to make space for key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // Insert key at its correct position
    }
}

int main() {
    int arr[] = {9, 5, 1, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

In this program, we define a function insertionSort() that sorts an array using the Insertion Sort algorithm. It starts by assuming the first element is already sorted and then iterates through the rest of the array. Each new element (key) is compared with the sorted part, and elements are shifted to make space for inserting the key at its correct position.

The algorithm uses a nested loop: the outer loop picks elements one by one, while the inner loop shifts elements in the sorted section until the correct position for the key is found. This guarantees that the left portion of the array stays sorted following each iteration.

Output

Sorted array: 1 3 4 5 9

Time and Space Complexity:

• Time Complexity: For Best Case: O(n) (when the array is already sorted). For Worst and Average Case: O(n²) (when the array is in reverse order or randomly sorted).
• Space Complexity: O(1) (since sorting is done in place with no extra memory usage).

Merge Sort in C++

The divide and conquer strategy is the basis for the sorting algorithm known as Merge Sort. It splits the array into smaller subarrays, sorts them, and then merges them back together in a sorted order. This technique guarantees a worst-case time complexity with O(n log n) and is effective for huge datasets.

#include <iostream>

// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int leftArr[n1], rightArr[n2];

    // Copy elements to temporary arrays
    for (int i = 0; i < n1; i++) 
        leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++) 
        rightArr[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;

    // Merge the temporary arrays back into the original array
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) 
            arr[k++] = leftArr[i++];
        else 
            arr[k++] = rightArr[j++];
    }

    // Copy remaining elements, if any
    while (i < n1) 
        arr[k++] = leftArr[i++];
    while (j < n2) 
        arr[k++] = rightArr[j++];
}

// Recursive Merge Sort function
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// Driver function
int main() {
    int arr[] = {8, 3, 7, 1, 9, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation of the code

Here in this code splits an array in half, sorts each half separately, and then merges the two halves using a recursive approach called Merge Sort. The mergeSort() function divides the array repeatedly until single-element subarrays are created. The merge() technique is then used to rebuild these sorted subarrays in sorted order.

When the items are combined back, they are kept in separate temporary arrays called leftArr and rightArr until ready to combine into one sorted array. This merging process guarantees that the individual pieces of an object's proper place within the full structure are precisely merged together after sorting has occurred. Hence, a consistent and efficient way of sorting is through the above.

Output

Sorted array: 1 3 5 7 8 9

Time and Space Complexity:

• Time Complexity: O(n log n) (since the array is repeatedly divided and merged).
• Space Complexity: O(n) (due to the use of temporary arrays for merging).

Quick Recap

• These classic algorithms reveal how sorting works internally.
• Bubble Sort is simple but slow; Insertion Sort is efficient for small/near-sorted data; Merge Sort offers guaranteed O(n log n).
• Understanding these strengthens your DSA & interview skills.

With its hybrid Introsort engine, std::sort() makes sorting in C++ both strong and efficient. C++ offers a variety of methods for sorting data, including built-in functions, lambdas, functors, and traditional algorithms like Bubble Sort, Insertion Sort, and Merge Sort, regardless of whether you're working with arrays, vectors, or custom objects. Gaining an understanding of the aforementioned strategies can help you perform better, gain a firm grasp of software development and programming interview requirements, and increase your knowledge of data structures.

Key Points to Remember

• std::sort() is the fastest and most preferred sorting method in C++, optimized using Introsort.
• Custom comparators (lambdas, functors) let you define your own sorting rules for any data type.
• Vectors are easier and more flexible to sort than arrays due to dynamic sizing and iterator support.
• Operator overloading and comparators are essential for sorting custom classes and objects.
• Classic algorithms such as Bubble sort, Insertion sort, and Merge Sort provide foundational knowledge on sorting to prepare the interviewer on your understanding of Data structures, Algorithms, and Software Engineering principles.

1. What is the sort function in C++?

The std::sort() function is an STL utility that rearranges elements in a given range. It can sort data in ascending, descending, or any custom order depending on the comparator you provide.

2. How do you use the sort function on an array?

Include the <algorithm> header and call:

 std::sort(arr, arr + n);

Here, arr is the starting address and arr + n points just past the last element.

3. Can the sort function sort in descending order?

Yes. To sort in descending order, pass std::greater<int>() as the comparator:

 std::sort(arr, arr + n, std::greater<int>());

4. Is it possible to sort part of an array using the sort function?

Absolutely. You can sort only a specific segment by defining a subrange:

 std::sort(arr + start, arr + end + 1);

Only the elements within that range will be rearranged.

5. How does the sort function compare elements by default?

By default, std::sort() uses the < operator to compare values, which results in ascending order.

6. What algorithm does std::sort use?

std::sort() uses Introsort, a hybrid algorithm that combines Quick Sort, Heap Sort, and Insertion Sort to ensure both speed and worst-case reliability.

7. How do I sort a std::vector?

Use the same function as arrays:

std::sort(vec.begin(), vec.end());

This sorts all elements between the beginning and end iterators in ascending order.