9 Ways To Sort Array In C++ (A Detailed Guide With Code Examples)

How To Sort Array In C++ Using Insertion Sort?

Insertion sort is a simple sorting algorithm that works by repeatedly taking an element from the unsorted portion of the array and inserting it into the correct position within the sorted portion. In other words, it builds the final sorted array one item at a time. Here's how insertion sort works:

• It starts by considering the first element of the array as the sorted portion.
• It then iterates through the remaining elements, inserting each element into its correct position within the already sorted portion.
• The algorithm continues this process until the entire array is sorted.

The algorithm iterates over the input listing, comparing each element to its adjoining values and transferring elements that are greater to the right.
This procedure is repeated till the entire array is sorted.

The Insertion Sort algorithm in C++ has the following syntax:

InsertionSort(p)
for j = 2 to length[p]
key = p[j]
i = j - 1
while i > 0 and p[i] > key
p[i + 1] = p[i]
i = i - 1
p[i + 1] = key

In this pseudocode,

• The character p refers to the array to be sorted using insertion sort.
• The for loop starts from the second element of the array and compares it with the preceding elements, moving them to the right till the correct position for the contemporary element (key) is determined.
• The key variable stores the element currently being sorted.
• The while loop shifts elements that are greater than the key to the right, making space for the key to be inserted into its correct position.

Note that the process in the pseudocode/syntax (of sorts) is repeated until the array at hand is sorted.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBpbnNlcnRpb25Tb3J0KGludCBhcnJbXSwgaW50IG4pIHsKaW50IHksIGtleSwgbTsKCi8vIExvb3AgdGhyb3VnaCB0aGUgYXJyYXkgc3RhcnRpbmcgZnJvbSB0aGUgc2Vjb25kIGVsZW1lbnQKZm9yICh5ID0gMTsgeSA8IG47IHkrKykgewprZXkgPSBhcnJbeV07Cm0gPSB5IC0gMTsKCi8vIFNoaWZ0IGVsZW1lbnRzIHRoYXQgYXJlIGdyZWF0ZXIgdGhhbiB0aGUga2V5IHRvIG9uZSBwb3NpdGlvbiBhaGVhZAp3aGlsZSAobSA+PSAwICYmIGFyclttXSA+IGtleSkgewphcnJbbSArIDFdID0gYXJyW21dOwptID0gbSAtIDE7Cn0KCi8vIEluc2VydCB0aGUga2V5IGF0IHRoZSBjb3JyZWN0IHBvc2l0aW9uCmFyclttICsgMV0gPSBrZXk7Cn0KfQoKaW50IG1haW4oKSB7CmludCBhcnJbXSA9IHs5LCAzLCA1LCAxLCA4fTsKaW50IG4gPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKLy8gU29ydCB0aGUgYXJyYXkgdXNpbmcgaW5zZXJ0aW9uIHNvcnQKaW5zZXJ0aW9uU29ydChhcnIsIG4pOwoKLy8gUHJpbnQgdGhlIHNvcnRlZCBhcnJheQpmb3IgKGludCB5ID0gMDsgeSA8IG47IHkrKykgewpjb3V0IDw8IGFyclt5XSA8PCAiICI7Cn0KCnJldHVybiAwOwp9

Output:

1 3 5 8 9

Explanation:

In the above C++ program,

1. We define an insertionSort() function, which takes an integer array arr and its size n (int type) as parameters. Inside this function-
   • We declare three integer variables, y, key, and m, where key will hold the current element we want to insert into the sorted portion of the array, while m helps in finding the correct position.
   • Next, we enter a for loop, starting from the second element of the array (y = 1, since the first element arr[0] is considered as sorted) up to the last element (y = n-1).
   • For each iteration of for loop, we store the element arr[y] in key variable and set m to y - 1, which represents the index of the previous element in the sorted portion.
   • Then, we enter a while loop to compare and shift elements if needed. If any element in the sorted portion is greater than key, it is shifted one position to the right to make room for key. This process continues as long as m is greater than or equal to 0 and arr[m] is larger than the key.
   • Outside the while loop, once the correct position is found, we insert key into arr[m + 1], which is the position just after the last shifted element.
   • The for loop continues iterating until all elements of the array are sorted.
2. Next, in the main() function, we declare an integer array arr and initialized with values {9, 3, 5, 1, 8}.
3. After that, we calculate the size of the array, which is stored in the variable n using the sizeof() operator.
4. We then call the insertionSort() function with the array arr and its size n as arguments to perform the sorting operation.
5. Finally, we print the sorted array using for loop with the cout command.

Time Complexity: The time complexity of Insertion Sort for the best case scenario is O(n). In the worst case, the time complexity is O(n^2).
Space Complexity: The space complexity of Insertion Sort is O(1).

Check out this amazing course to become the best version of the C++ programmer you can be.

How To Sort An Array In C++ Using Selection Sort?

Selection sort is a straightforward sorting algorithm in C++ that works by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted subarray itself. Sounds confusing? Well, here is how selection sort works:

• The algorithm maintains two subarrays within the given array: a sorted subarray and an unsorted subarray.
• Note that initially, the unsorted subarray initially contains the full unsorted array, and the sorted subarray is empty (assumed to be at the beginning of the array).
• The algorithm finds the minimum/ least element of the unsorted subarray in every iteration, and swaps it with the element at the beginning of the unsorted subarray.
• This marks the beginning of the sorted portion of the array. This process continues until the unsorted subarray is empty and the entire array is sorted.

The Selection Sort algorithm in C++ has the following syntax:

void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// to find the minimum element in the unsorted part of the array
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;}
}
//to swap the minimum element with the first element of the unsorted part
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}

Here,

• The arr[] represents an integer array of size n, both of which are parameters for the selectionSort() function. It sorts the array in sort ascending order.
• The for keyword marks the beginning of for loop. We have a set of nested for loops, where the  outer for loop traverses the array one current element at a time from index 0 to index n-2.
• Inner loop compares current element with the next element, to help decide if a swap must be made.
• The if statement inside the inner loop updates min_index if a smaller element is found.
• Once the minimum element is found, it is swapped with the first element of the unsorted part, effectively moving it to the beginning of the array.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgc2VsZWN0aW9uU29ydChpbnQgYXJyW10sIGludCBuKSB7CmZvciAoaW50IGggPSAwOyBoIDwgbiAtIDE7IGgrKykgewppbnQgbWluX2luZGV4ID0gaDsKCi8vIEZpbmQgdGhlIGluZGV4IG9mIHRoZSBtaW5pbXVtIGVsZW1lbnQgaW4gdGhlIHVuc29ydGVkIHBhcnQKZm9yIChpbnQgaiA9IGggKyAxOyBqIDwgbjsgaisrKSB7CmlmIChhcnJbal0gPCBhcnJbbWluX2luZGV4XSkgewptaW5faW5kZXggPSBqOwp9Cn0KCi8vIFN3YXAgdGhlIGZvdW5kIG1pbmltdW0gZWxlbWVudCB3aXRoIHRoZSBmaXJzdCBlbGVtZW50IG9mIHRoZSB1bnNvcnRlZCBwYXJ0CmludCB0ZW1wID0gYXJyW2hdOwphcnJbaF0gPSBhcnJbbWluX2luZGV4XTsKYXJyW21pbl9pbmRleF0gPSB0ZW1wOwp9Cn0KCmludCBtYWluKCkgewppbnQgYXJyW10gPSB7NSwgMywgOCwgNCwgMn07CmludCBuID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKCmNvdXQgPDwgIk9yaWdpbmFsIGFycmF5OiAiOwpmb3IgKGludCBoID0gMDsgaCA8IG47IGgrKykgewpjb3V0IDw8IGFycltoXSA8PCAiICI7Cn0KY291dCA8PCBlbmRsOwoKLy8gU29ydCB0aGUgYXJyYXkgdXNpbmcgc2VsZWN0aW9uIHNvcnQKc2VsZWN0aW9uU29ydChhcnIsIG4pOwoKY291dCA8PCAiU29ydGVkIGFycmF5OiAiOwpmb3IgKGludCBoID0gMDsgaCA8IG47IGgrKykgewpjb3V0IDw8IGFycltoXSA8PCAiICI7Cn0KY291dCA8PCBlbmRsOwoKcmV0dXJuIDA7Cn0=

Output:

Original array: 5 3 8 4 2
Sorted array: 2 3 4 5 8

Explanation:

In the sample C++ code, we show how to sort an array of numbers in ascending order using the selection sort method.

1. To begin with, we define a selectionSort() function to perform the selection sort algorithm. It takes two parameters, i.e., an integer array arr, and the size of the array, i.e., variable n.
2. Inside the selectionSort() function, we have a set of nested for loops:
   • The outer for loop iterates from index 0 to n - 1. In each iteration, it first selects the next position in the sorted portion of the array, and places the minimum element from the unsorted portion in this place.
   • Here, we declare and initialize an integer variable min_index to the value of h. This represents the index of the current minimum element, which is initially assumed to be the first element in the unsorted part of the array.
   • Then, we use an inner for loop to iterate from h + 1 to n. In every iteration, it searches the unsorted part of the array for the smallest element by comparing each element to the current minimum (arr[min_index]) and updates min_index whenever a smaller element is found.
   • Next, we have an if-statement inside the inner loop, which checks if an element is smaller than the current minimum (arr[j] < arr[min_index]). If this condition holds true, then min_index is modified to hold the value of j, thus ensuring that min_index always refers to the index of the smallest element of the unsorted section.

   • After finding the minimum element in the unsorted part, we swap this element with the first element of the unsorted portion. To do this, we temporarily store the value at index h in a variable temp, then assign the value at min_index to arr[h], and finally set arr[min_index] to temp.

3. Then, in the main() function, we declare an integer array arr and initialized with unsorted values {5, 3, 8, 4, 2}. After that, we calculate the size of the array using the sizeof() operator and store it in variable n.
4. The code then proceeds to print the elements of the array before sorting, using the cout command and a for loop.
5. Next, we call the selectionSort() function with the arr array and its size n as arguments to perform the sorting.
6. Finally, we use a for loop with a cout command to print the sorted array.

Time Complexity: The best-case time complexity is O(n^2), and the worst-case time complexity is O(n^2).
Space Complexity: The space complexity of the Selection Sort is O(1).

Level up your coding skills with the 100-Day Coding Sprint at Unstop and earn your bragging rights today!

How To Sort An Array In C++ Using Quicksort?

Quicksort is a widely used sorting algorithm in C++ that follows the "divide-and-conquer" approach. Meaning, it selects a pivot element, divides the array into sub-arrays (one with elements smaller than the pivot and other with remaining), and recursively sorts (conquers) the sub-arrays. Here’s how quicksort works:

• Under this technique, a pivot element is chosen from the array. This pivot can be any element (commonly the first, last, or middle element, or even a randomly selected one).
• The array undergoes a partitioning step in which it is divided into sub-arrays based mostly on a delegated pivot element.
• Elements smaller than the pivot are grouped into the left sub-array, whilst elements equal to or more than the pivot are positioned inside the right sub-array.
• This partitioning is completed by using the use of two pointers placed at the ends of the sub-array, gradually shifting towards each other till they converge.
• The left and right sub-arrays are then recursively sorted using the same manner using the quicksort() function.
• Finally, while all the sub-arrays have been sorted, the array is organized in ascending order.

The Quick Sort algorithm in C++ has the following syntax:

void quickSort(int arr[], int left, int right) {
//if sub-array has less than 2 elements
if (left >= right) {
return;
}
int pivot = arr[(left + right) / 2];
int i = left, j = right; // partition sub-array
while (i <= j) {
while (arr[i] < pivot) {
i++;}
while (arr[j] > pivot) {
j--;}
if (i <= j) {
std::swap(arr[i], arr[j]);
i++;
j--;}
}
quickSort(arr, left, j); // recursively sort left and right sub-arrays
quickSort(arr, i, right);
}

Here,

• Integer array arr[] refers to the array to be sorted, with integer variables left and right representing the subarray's leftmost and rightmost indexes, respectively. The quickSort() function accepts them as parameters.
• Integer variable pivot refers to the pivot element, i.e., the sub-array's middle element.
• We use while loops and if-statements to check conditions and carry out the sorting.

By swapping elements that might be on the incorrect side of the pivot, the sub-array is ultimately divided into two sub-arrays. The two ensuing sub-arrays are then sorted recursively using the QuickSort function.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdm9pZCBxdWlja1NvcnQoaW50IGFycltdLCBpbnQgbGVmdCwgaW50IHJpZ2h0KSB7CmlmIChsZWZ0ID49IHJpZ2h0KSB7CnJldHVybjsKfQoKaW50IHBpdm90ID0gYXJyW2xlZnRdOyAvLyBDaG9vc2UgdGhlIHBpdm90IGFzIHRoZSBsZWZ0bW9zdCBlbGVtZW50CmludCBpID0gbGVmdCArIDE7IC8vIFN0YXJ0IGZyb20gdGhlIGVsZW1lbnQgbmV4dCB0byB0aGUgcGl2b3QKaW50IGogPSByaWdodDsKCndoaWxlIChpIDw9IGopIHsKLy8gRmluZCBhbiBlbGVtZW50IGdyZWF0ZXIgdGhhbiB0aGUgcGl2b3QKd2hpbGUgKGkgPD0gaiAmJiBhcnJbaV0gPD0gcGl2b3QpIHsKaSsrOwp9Ci8vIEZpbmQgYW4gZWxlbWVudCBzbWFsbGVyIHRoYW4gdGhlIHBpdm90CndoaWxlIChpIDw9IGogJiYgYXJyW2pdID4gcGl2b3QpIHsKai0tOwp9CmlmIChpIDwgaikgewpzdGQ6OnN3YXAoYXJyW2ldLCBhcnJbal0pOwp9Cn0KCi8vIE1vdmUgdGhlIHBpdm90IHRvIGl0cyBjb3JyZWN0IHBvc2l0aW9uCnN0ZDo6c3dhcChhcnJbbGVmdF0sIGFycltqXSk7CgovLyBSZWN1cnNpdmVseSBzb3J0IHRoZSBzdWItYXJyYXlzCnF1aWNrU29ydChhcnIsIGxlZnQsIGogLSAxKTsKcXVpY2tTb3J0KGFyciwgaiArIDEsIHJpZ2h0KTsKfQoKaW50IG1haW4oKSB7CmludCBhcnJbXSA9IHs5LCA0LCAyLCA3LCAxLCA1LCAzfTsKaW50IHNpemUgPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKcXVpY2tTb3J0KGFyciwgMCwgc2l6ZSAtIDEpOwoKc3RkOjpjb3V0IDw8ICJTb3J0ZWQgYXJyYXk6ICI7CmZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKSB7CnN0ZDo6Y291dCA8PCBhcnJbaV0gPDwgIiAiOwp9CnN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CgpyZXR1cm4gMDsKfQ==

Output:

Sorted array: 1 2 3 4 5 7 9

Explanation:

In the sample C++ program above,

1. We define the quickSort() function to implement the QuickSort algorithm. It takes three parameters, i.e., arr (an integer array), left (index of the leftmost element in the sub-array to be sorted), and right (index of the rightmost element in the sub-array to be sorted).
2. Inside the quickSort() function-
   • We use an if-statement  to check the base case for the recursive call. If the left index is greater than or equal to the right index, it means the sub-array has only one element or no elements. In such cases, the function returns immediately as there's nothing to sort.
   • If not, then the function chooses the leftmost element (arr[left]) as the pivot element, i.e., int pivot = arr[left].
   • Next, we initialize two pointers: i starts at left + 1 (just after the pivot), and j starts at right (the last element of the sub-array). These pointers are used to scan the array from both ends.
   • We then initiate three nested while loops. The outermost loop continues until i <= j holds true.
   • The two inner loops search for two elements to swap, i.e., an element greater than the pivot on the left side (arr[i]) and an element smaller than or equal to the pivot on the right side (arr[j]).
   • The while loop that increments i searches for the element greater than the pivot, and the while loop that decrements j searches for the element smaller than or equal to the pivot.
   • Then, an if statement checks condition (i<j), which means the two elements to be swapped have been found. The elements at positions i and j are then swapped using std::swap.
   • The while loop continues until i becomes greater than j, indicating that all necessary swaps have been performed.
   • After the loop, the pivot element (arr[left]) is swapped with the element at position j. This places the pivot element in its correct sorted position.
   • Later, we apply recursion by invoking quickSort() multiple times to sort the sub-arrays positioned on the left and right sides of the pivot element. The process repeats until all sub-arrays are sorted.
3. Then, in the main() function, we declare an integer array arr and initialize with values {9, 4, 2, 7, 1, 5, 3}. After that, we calculate the size of the array using sizeof() operator and store it in variable n.
4. Next, we call the quickSort() function with the arr array, left initialized to 0, and right initialized to size - 1, as arguments. In other words, the entire array is the range for the function, which it sorts in place.
5. Finally, we print the elements of the array after sorting using the cout command and a for loop to demonstrate the sorted order.

Time Complexity: The best-case scenario has a time complexity of O(n log n), and the worst-case scenario time complexity is O(n^2).
Space Complexity: The space complexity of Quick Sort is O(log n).

How To Sort Array In C++ Using Merge Sort?

Merge sort is another sorting algorithm in C++ that also follows the "divide-and-conquer" approach. It divides the input array into two equal halves and continues the division until the subarrays have only one element each (considered sorted).

It then recursively sorts the subarrays individually to produce a single sorted array by merging the subarrays back together. The elements from the two subarrays are compared throughout the merging process, and then they are added to the original array in the proper order.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gTWVyZ2UgdHdvIHNvcnRlZCBzdWJhcnJheXMgaW50byBhIHNpbmdsZSBzb3J0ZWQgYXJyYXkKdm9pZCBtZXJnZShpbnQgYXJyW10sIGludCBsZWZ0W10sIGludCBsZWZ0U2l6ZSwgaW50IHJpZ2h0W10sIGludCByaWdodFNpemUpIHsKaW50IGkgPSAwLCBqID0gMCwgayA9IDA7CgovLyBDb21wYXJlIGVsZW1lbnRzIGZyb20gbGVmdCBhbmQgcmlnaHQgc3ViYXJyYXlzIGFuZCBtZXJnZSB0aGVtIGludG8gdGhlIG9yaWdpbmFsIGFycmF5CndoaWxlIChpIDwgbGVmdFNpemUgJiYgaiA8IHJpZ2h0U2l6ZSkgewppZiAobGVmdFtpXSA8PSByaWdodFtqXSkgewphcnJba10gPSBsZWZ0W2ldOwppKys7Cn0gZWxzZSB7CmFycltrXSA9IHJpZ2h0W2pdOwpqKys7Cn0KaysrOwp9CgovLyBDb3B5IHRoZSByZW1haW5pbmcgZWxlbWVudHMgb2YgbGVmdCBzdWJhcnJheQp3aGlsZSAoaSA8IGxlZnRTaXplKSB7CmFycltrXSA9IGxlZnRbaV07CmkrKzsKaysrOwp9CgovLyBDb3B5IHRoZSByZW1haW5pbmcgZWxlbWVudHMgb2YgcmlnaHQgc3ViYXJyYXkKd2hpbGUgKGogPCByaWdodFNpemUpIHsKYXJyW2tdID0gcmlnaHRbal07CmorKzsKaysrOwp9Cn0KCi8vIE1lcmdlIHNvcnQgaW1wbGVtZW50YXRpb24Kdm9pZCBtZXJnZVNvcnQoaW50IGFycltdLCBpbnQgc2l6ZSkgewppZiAoc2l6ZSA8IDIpCnJldHVybjsKCmludCBtaWQgPSBzaXplIC8gMjsKaW50IGxlZnRbbWlkXTsKaW50IHJpZ2h0W3NpemUgLSBtaWRdOwoKLy8gRGl2aWRlIHRoZSBhcnJheSBpbnRvIHR3byBoYWx2ZXMKZm9yIChpbnQgaSA9IDA7IGkgPCBtaWQ7IGkrKykKbGVmdFtpXSA9IGFycltpXTsKZm9yIChpbnQgaSA9IG1pZDsgaSA8IHNpemU7IGkrKykKcmlnaHRbaSAtIG1pZF0gPSBhcnJbaV07CgovLyBSZWN1cnNpdmVseSBzb3J0IHRoZSB0d28gaGFsdmVzCm1lcmdlU29ydChsZWZ0LCBtaWQpOwptZXJnZVNvcnQocmlnaHQsIHNpemUgLSBtaWQpOwoKLy8gTWVyZ2UgdGhlIHNvcnRlZCBoYWx2ZXMKbWVyZ2UoYXJyLCBsZWZ0LCBtaWQsIHJpZ2h0LCBzaXplIC0gbWlkKTsKfQoKLy8gVXRpbGl0eSBmdW5jdGlvbiB0byBwcmludCBhbiBhcnJheQp2b2lkIHByaW50QXJyYXkoaW50IGFycltdLCBpbnQgc2l6ZSkgewpmb3IgKGludCBpID0gMDsgaSA8IHNpemU7IGkrKykKY291dCA8PCBhcnJbaV0gPDwgIiAiOwpjb3V0IDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewppbnQgYXJyW10gPSB7MTIsIDExLCAxMywgNSwgNiwgN307CmludCBzaXplID0gc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKTsKCmNvdXQgPDwgIk9yaWdpbmFsIGFycmF5OiAiOwpwcmludEFycmF5KGFyciwgc2l6ZSk7CgptZXJnZVNvcnQoYXJyLCBzaXplKTsKCmNvdXQgPDwgIlNvcnRlZCBhcnJheTogIjsKcHJpbnRBcnJheShhcnIsIHNpemUpOwoKcmV0dXJuIDA7Cn0=

Output:

Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13

Explanation:

In the above C++ program,

1. We define a merge() function  to merge two sorted subarrays into a single sorted array. It takes five parameters, i.e., the original array arr[], two sorted subarrays left[] and right[], and their respective sizes leftSize and rightSize. 
2. Inside the function-
   • We declare three integer variables, i, j, and k, to track the current index in the left, right, and original arrays, respectively, as we merge the two subarrays.

   • Then, we use a while loop to compare elements from the left and right subarrays. Using an if-else statement, we check if the element in the left subarray is smaller or equal to the element in the right subarray.

   • If the condition is true, we place the current element arr[k] in the original array at i-th position (left[i]), and increment both i and k.

   • If the element from the right subarray is smaller, we place it in the original array, and increment j and k.

   • Once one of the subarrays is fully traversed, we use two additional while loops to copy any remaining elements from the left or right subarray into the original array.
3. Next, we define a mergeSort() function to implement the merge sort algorithm. It takes two parameters, i.e., the original array arr and its size size. Inside the mergeSort() function-
   • We use an if statement to check the condition if the size of the array is less than 2. If it is, then the function returns immediately as there's nothing to sort.
   • If the condition is false, we calculate the midpoint mid of the array and declare two new arrays, left (with the size mid) and right (with capacity of size-mid), to hold the left and right half of the original array, respectively.
   • We then use two for loops to divide the original array into two halves by copying elements at index less than mid, in the left subarray and the remaining in the right subarray.
   • Next, we sort the two subarray by recursively calling the mergeSort() function on them.
   • Once both halves are sorted, we call the merge() function to merge the sorted subarrays back into the original array.
4. Next, we define a printArray() function, which prints the elements of an array using a for loop and the cout command.
5. In the main() function, we declare an integer array arr and initialize it with integer values {12, 11, 13, 5, 6, 7}. Then, we calculate the size of the array using the sizeof() operatorand store that in variable n.
6. We call the mergeSort() function with the arr array and its size as arguments, to sort the entire array. Afte that, we print it to the console using the printArray() function.

Time Complexity: The best-case time complexity is O(n log n), and the worst-case time complexity is O(n log n).
Space Complexity: The space complexity of Merge Sort is O(n).

How To Sort Data in C++ With Custom Function?

Instead of using the built-in comparison operations provided by the C++, you can employ a user-defined function to sort data based on specific requirements. This involves grouping together data components based on a specific comparison criterion:

• Say you have a list of complex items, and you want to reserve them by means of a positive attribute or set of attributes that the computer language's integrated sorting mechanism does not support.
• In this case, you can create a custom function that accepts two objects as input and outputs -1, 0, or 1 depending on whether the desired attribute values of the two objects compare favorably.
• The language's sorting algorithm can then be used with this custom function as an argument to decide the order of the items in the resulting sorted list.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRGVmaW5lIHRoZSBjdXN0b20gc29ydGluZyBmdW5jdGlvbgpib29sIGN1c3RvbVNvcnQoaW50IGEsIGludCBiKSB7Ci8vIFNvcnQgZXZlbiBudW1iZXJzIGZpcnN0CmlmIChhICUgMiA9PSAwICYmIGIgJSAyID09IDEpIHsKcmV0dXJuIHRydWU7Cn0KLy8gU29ydCBvZGQgbnVtYmVycyBsYXN0CmVsc2UgaWYgKGEgJSAyID09IDEgJiYgYiAlIDIgPT0gMCkgewpyZXR1cm4gZmFsc2U7Cn0KLy8gRm9yIGV2ZW4gb3Igb2RkIG51bWJlcnMsIHNvcnQgaW4gYXNjZW5kaW5nIG9yZGVyCmVsc2UgewpyZXR1cm4gYSA8IGI7Cn0KfQoKaW50IG1haW4oKSB7CmludCBhcnJbXSA9IHs0LCAxLCA1LCAyLCAzLCA2fTsKaW50IG4gPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKLy8gU29ydCB0aGUgYXJyYXkgdXNpbmcgdGhlIGN1c3RvbSBzb3J0aW5nIGZ1bmN0aW9uCnNvcnQoYXJyLCBhcnIgKyBuLCBjdXN0b21Tb3J0KTsKCi8vIFByaW50IHRoZSBzb3J0ZWQgYXJyYXkgdG8gdGhlIGNvbnNvbGUKZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKY291dCA8PCBhcnJbaV0gPDwgIiAiOwp9CmNvdXQgPDwgZW5kbDsKCnJldHVybiAwOwp9

Output

2 4 6 1 3 5

Explanation:

In the example above,

1. We first define a customSort() function for sorting integers, which takes two integers, a and b, as parameters and returns a boolean value.
2. The logic we implement in the customSort() function is:
   
   • If a is even and b is odd, the function returns true, meaning a should come before b.
   • If a is odd and b is even, the function returns false, indicating that b should come before a.
   • For any other case, i.e., if both a and b are either even or odd, the function returns a < b to sort them in ascending order.
3. In the main() function, we initialize an integer array arr with values {4, 1, 5, 2, 3, 6} and calculate its size n using the sizeof() operator.
4. We then call the sort() function from the C++ Standard Library to sort the array. It takes three arguments: arr (the start of the array), arr+n (the end of the array), and out custom comparison function (customSort()), which defines the sorting logic.
5. After that, we use a for loop (iterates from 0 to n-1) with a cout command to print each element of sorted array followed by a sapce.

Partial Sort Function To Sort An Array In C++

In C++, a partial sort is an algorithmic operation that sorts only a subset of a specified sequence or container rather than the complete collection. This allows you to bring the smallest (or largest, depending on the sorting order) elements to the front of the range while not necessarily sorting the entire range. The std::partial_sort function from the C++ Standard Library performs this task efficiently.

The syntax for Partial Sorting using std::partial_sort in C++ is as follows:

#include <algorithm>
std::partial_sort(first, middle, last);

Here:

• first: An iterator pointing to the beginning of the range to be partially sorted.
• middle: An iterator pointing to the element that marks the end of the partially sorted range. This is the position where the smallest (middle - first) elements will be placed in sorted order.
• last: An iterator pointing to the end of the range to be partially sorted.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKaW50IG1haW4oKSB7CmludCBudW1iZXJzW10gPSB7OSwgNSwgMiwgOCwgMSwgNywgNiwgMywgNH07CmludCBrID0gNDsgLy8gTnVtYmVyIG9mIGVsZW1lbnRzIHRvIGJlIHBhcnRpYWxseSBzb3J0ZWQKCi8vIFBhcnRpYWxseSBzb3J0IHRoZSBmaXJzdCAnaycgZWxlbWVudHMgaW4gYXNjZW5kaW5nIG9yZGVyCnN0ZDo6cGFydGlhbF9zb3J0KG51bWJlcnMsIG51bWJlcnMgKyBrLCBudW1iZXJzICsgOSk7CgovLyBQcmludCB0aGUgcGFydGlhbGx5IHNvcnRlZCBlbGVtZW50cwpmb3IgKGludCBpID0gMDsgaSA8IGs7IGkrKykgewpzdGQ6OmNvdXQgPDwgbnVtYmVyc1tpXSA8PCAiICI7Cn0Kc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCnJldHVybiAwOwp9

Output

1 2 3 4

Explanation

In this code,

1. In the main() function, we declare and initialize an integer array called numbers, with the values {9, 5, 2, 8, 1, 7, 6, 3, 4}.
2. We also declare an integer variable, k, and initialize it with the value of 4, indicating the number of elements to be partially sorted.
3. Next, we call the std::partial_sort function to partially sort the first 'k' elements in ascending order. It takes three parameters-
   • The initial parameter numbers, which is the beginning of the range to be partially sorted, representing the memory address of the first element in the array (numbers).
   • The second parameter numbers + k, which is the end of the range to be sorted. This means we are sorting up to the first k elements.
   • The third parameter numbers + 9, which specifies the end of the entire array. The function will use this to understand the bounds of the full array but only partially sort the specified range.
   • The function will sort the first 'k' elements of the numbers array in ascending order, but the remaining elements beyond the 'k'-th position will not be sorted and may appear in any order.
4. After performing the partial sort, we print the first k elements of the array. We use a for loop to iterate from 0 to k - 1, outputting each element followed by a space using the cout command.

Complexity Analysis

Given below is a comparison table, arranged in descending order from best to least based on average-case time complexity and space complexity:

As we can notice from the above analysis, sort() and qsort() functions have the best average-case time complexity of O(n log n) with efficient space usage, followed by Merge Sort with similar time complexity but higher space requirements.

Quicksort also offers good average-case time complexity but has the potential for worst-case performance. Bubble Sort and Insertion Sort have poorer time complexity but minimal space needs.

Looking for mentors? Find the perfect mentor for select experienced coding & software experts here.

Conclusion

Sorting an array in C++ entails utilizing sorting algorithms like std::sort(), std::partial_sort(), bubble sort, insertion sort, selection sort, merge sort, or quicksort. Functions like std::sort() and std::partial_sort(), which are useful for quick sorting operations, are included in the C++ Standard Library.

When wondering how to sort an array in C++, all you have to do is choose the right algorithm according to your precise requirements. It is simpler to find and access individual elements when elements in an array are arranged in a particular order, thanks to sorting. Sorting arrays also makes the search operation easier. Overall, sorting arrays is a fundamental operation that offers a wide range of advantages in terms of data organization, search efficiency, data analysis, algorithmic efficiency, and result display.

Also read- 51 C++ Interview Questions For Freshers & Experienced (With Answers)

Frequently Asked Questions

Q. How to sort a 2D array in cpp using the sort function?

To sort a 2D array in C++, we need to use the std::sort function.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgoKYm9vbCBjb21wYXJlUm93cyhjb25zdCBzdGQ6OnZlY3RvcjxpbnQ+JiByb3cxLCBjb25zdCBzdGQ6OnZlY3RvcjxpbnQ+JiByb3cyKSB7CnJldHVybiByb3cxWzBdIDwgcm93MlswXTsgLy8gU29ydCBiYXNlZCBvbiB0aGUgZmlyc3QgY29sdW1uCn0KCmludCBtYWluKCkgewovLyBFeGFtcGxlIDJEIGFycmF5CnN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPGludD4+IGFyciA9IHsKezMsIDIsIDF9LAp7MSwgNCwgMn0sCnsyLCAzLCA2fQp9OwoKLy8gU29ydCB0aGUgMkQgYXJyYXkgYmFzZWQgb24gdGhlIGZpcnN0IGNvbHVtbgpzdGQ6OnNvcnQoYXJyLmJlZ2luKCksIGFyci5lbmQoKSwgY29tcGFyZVJvd3MpOwoKLy8gUHJpbnQgdGhlIHNvcnRlZCBhcnJheQpmb3IgKGNvbnN0IGF1dG8mIHJvdyA6IGFycikgewpmb3IgKGNvbnN0IGF1dG8mIGVsZW1lbnQgOiByb3cpIHsKc3RkOjpjb3V0IDw8IGVsZW1lbnQgPDwgIiAiOwp9CnN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7Cn0KCnJldHVybiAwOwp9

Output:

1 4 2
2 3 6
3 2 1

Explanation:

In this example,

1. The code first includes the iostream, algorithm, and vector header files. These header files provide the necessary functions and classes for the code to work.
2. We then define a compareRows() function that takes two 2D arrays as input and returns true if the first array is less than the second array based on the first column. This function is used by the std::sort() algorithm to sort the 2D array.
3. In the main() function, we declare a 2D array of integers and assign it some values.
4. We then call the std::sort() function to sort the 2D array based on the first column. This function takes the beginning and end iterators of the array, as well as a comparison function, as input.
5. The comparison function is used to determine the order of the elements in the array.
6. Finally, we use a for loop to iterate through the sorted 2D array and the cout command to print each row to the console.

Q. How to sort an array in C++ using begin and end?

You can utilize the std::sort algorithm from the algorithm header in C++ to sort an array using the begin and end iterators. The std::sort() function takes two iterators as arguments to specify the range of elements to be sorted. The begin() and end() functions are used to obtain these iterators.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKaW50IG1haW4oKSB7CmludCBhcnJbXSA9IHs1LCAyLCA4LCAxLCA5fTsKaW50IHNpemUgPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOyAvLyBEZXRlcm1pbmUgdGhlIHNpemUgb2YgdGhlIGFycmF5CgovLyBTb3J0IHRoZSBhcnJheSB1c2luZyBiZWdpbiBhbmQgZW5kCnN0ZDo6c29ydChzdGQ6OmJlZ2luKGFyciksIHN0ZDo6ZW5kKGFycikpOwoKLy8gUHJpbnQgdGhlIHNvcnRlZCBhcnJheQpmb3IgKGludCBpID0gMDsgaSA8IHNpemU7ICsraSkgewpzdGQ6OmNvdXQgPDwgYXJyW2ldIDw8ICIgIjsKfQoKcmV0dXJuIDA7Cn0=

Output:

1 2 5 8 9

Explanation:

1. The code first includes the <iostream> and <algorithm> header files. These header files provide the necessary functions and classes for the code to work.
2. in the main() function, we declare an array of integers and assign it some values.
3. We then use the std::sort() algorithm to sort the array using the begin() and end() iterators. The begin() iterator points to the beginning of the array, and the end() iterator points to the end of the array.
4. Finally, using a for loop we iterate through the sorted array and the cout command to print each element to the console.

Q. How to sort two arrays in one array?

One way to sort two arrays into a single array is by first combining the two arrays and then sorting the merged array. 

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKaW50IG1haW4oKSB7CmludCBhcnIxW10gPSB7NSwgMiwgOH07CmludCBhcnIyW10gPSB7MSwgOSwgM307CgppbnQgc2l6ZTEgPSBzaXplb2YoYXJyMSkgLyBzaXplb2YoYXJyMVswXSk7CmludCBzaXplMiA9IHNpemVvZihhcnIyKSAvIHNpemVvZihhcnIyWzBdKTsKCmludCBtZXJnZWRTaXplID0gc2l6ZTEgKyBzaXplMjsKaW50IG1lcmdlZFttZXJnZWRTaXplXTsKCi8vIE1lcmdlIHRoZSBhcnJheXMKc3RkOjptZXJnZShhcnIxLCBhcnIxICsgc2l6ZTEsIGFycjIsIGFycjIgKyBzaXplMiwgbWVyZ2VkKTsKCi8vIFNvcnQgdGhlIG1lcmdlZCBhcnJheQpzdGQ6OnNvcnQobWVyZ2VkLCBtZXJnZWQgKyBtZXJnZWRTaXplKTsKCi8vIFByaW50IHRoZSBzb3J0ZWQgbWVyZ2VkIGFycmF5CmZvciAoaW50IGkgPSAwOyBpIDwgbWVyZ2VkU2l6ZTsgKytpKSB7CnN0ZDo6Y291dCA8PCBtZXJnZWRbaV0gPDwgIiAiOwp9CgpyZXR1cm4gMDsKfQ==

Output:

1 2 3 5 8 9

Explanation:

In this example,

1. We declare and initialize two arrays, arr1, and arr2, in the main() function.
2. Then, we calculate the size of both arrays and store them in two different variables, i.e., size1 and size2.
3. Using the addition operator, we add the sizes of the two arrays and store them in a new variable, mergedSize. We then use this size to declare a new array called merged to store the merged array.
4. Next, we use the std::merge() algorithm to merge the two arrays into the merged array.
5. We then call the std::sort() function to sort the merged array.
6. Finally, we use a for loop and the cout command to print the collection of elements of the sorted merged array to the console.

Q. How do you write a custom sort function in CPP?

To write a custom sort function in C++, you can use the std::sort() algorithm with a custom comparison function. The custom comparison function takes two elements as input and returns true if the first element is less than the second element and false otherwise. Let's look at an example of a custom sort function that sorts an array of integers in descending order.

Code Example:

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKYm9vbCBjb21wYXJlKGludCBhLCBpbnQgYikgewpyZXR1cm4gYSA+IGI7Cn0KCmludCBtYWluKCkgewppbnQgYXJyW10gPSB7MSwgNSwgMiwgOCwgOX07CgovLyBTb3J0IHRoZSBhcnJheSBpbiBkZXNjZW5kaW5nIG9yZGVyCnN0ZDo6c29ydChzdGQ6OmJlZ2luKGFyciksIHN0ZDo6ZW5kKGFyciksIGNvbXBhcmUpOwoKLy8gUHJpbnQgdGhlIHNvcnRlZCBhcnJheQpmb3IgKGludCBpID0gMDsgaSA8IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSk7ICsraSkgewpzdGQ6OmNvdXQgPDwgYXJyW2ldIDw8ICIgIjsKfQoKcmV0dXJuIDA7Cn0=

Output:

9 8 5 2 1

Explanation:

1. This code first defines a custom comparison function called compare(). It takes two integers as input and returns true if the first integer is greater than the second integer and false otherwise.
2. In the main() function, we declare an array of integers called arr and initialize it with the values 1, 5, 2, 8, and 9.
3. We then sort this array in descending order using the std::sort() algorithm. In the sort function, the std::begin() iterator points to the beginning of the array, and the std::end() iterator points to the end of the array.
4. The std::sort() algorithm will sort the array elements in descending order using the compare() function.
5. Finally, we print the sorted output array using a for loop and the cout command.

This compiles our discussion on how to sort an array in C++. You might also be interested in reading the following:

1. References In C++ | Declare, Types, Properties & More (+Examples)
2. Virtual Function In C++ | A Comprehensive Guide For All (+Examples)
3. Array Of Objects In C++ | A Complete Guide To Creation (Using Examples)
4. Inline Function In C++ | Declare, Working, Examples & More!
5. C++ Type Conversion & Type Casting Demystified (With Examples)