Functioning as an advanced sorting technique, much like systematically combining well-arranged puzzle pieces, merge sort employs a divide-and-conquer strategy to sort an array efficiently. It shines particularly in effectively managing large datasets while maintaining the stability of equal elements’ relative order.

Merge Sort Algorithm

The crux of merge sort algorithm involves breaking the array into smaller sub-arrays, sorting each sub-array, and then merging them back together. This merging step is where merge sort’s power lies.

Working of Merge Sort

To understand the process, let’s dig into an example array: arr[] = {38, 27, 43, 3, 9, 82, 10}

Pass 1: Divide

Array: 38    27    43    3    9    82    10

Divide: Firstly, Split array into smaller sub-arrays.

• [38]    [27]    [43]    [3]    [9]    [82]    [10]

Pass 2: Merge

Array: [38]    [27]    [43]    [3]    [9]    [82]    [10]

Merge: Then, Combine and sort pairs of sub-arrays.

• [27, 38]    [3, 43]    [9, 82]    [10]

Pass 3: Merge

Array: [27, 38]    [3, 43]    [9, 82]    [10]

Merge: To preceed, Combine and sort larger sub-arrays.

• [3, 27, 38, 43]    [9, 10, 82]

Pass 4 (Final Pass): Merge

Array: [3, 27, 38, 43]    [9, 10, 82]

Merge: Combine the last remaining sub-arrays.

• [3, 9, 10, 27, 38, 43, 82]

Finally, The array is now fully sorted.

Code in C++

This table explains each step of the Merge Sort algorithm implementation in C++ along with relevant code snippets.

Step	Code	Explanation
1	#include <iostream>	To begin, including necessary headers.
2	#include <vector>	Include the vector library for dynamic arrays.
3	using namespace std;	Utilize the standard namespace for simplicity.
4	void merge(vector<int>& arr, int low, int mid, int high) {…}	Now, define the merge function to sort sub-arrays.
5	int n1 = mid – low + 1;	Furthermore, calculate the size of the first sub-array.
6	int n2 = high – mid;	Calculate the size of the second sub-array.
7	vector<int> left(n1), right(n2);	Create temp vectors for sub-arrays.
8	for (int i = 0; i < n1; i++) {…}	Copy data to temp left sub-array.
9	for (int j = 0; j < n2; j++) {…}	Copy data to temp right sub-array.
10	int i = 0, j = 0, k = low;	Set indices for merging sub-arrays.
11	while (i < n1 && j < n2) {…}	Progress to merging by comparing elements.
12	if (left[i] <= right[j]) {…}	Place smaller element in array.
13	arr[k++] = left[i++];	Copy element from left sub-array.
14	else {…}	Alternatively, place element from right sub-array.
15	arr[k++] = right[j++];	Copy element from right sub-array.
16	while (i < n1) {…}	Continue copying remaining left sub-array elements.
17	arr[k++] = left[i++];	Copy remaining elements to array.
18	while (j < n2) {…}	Similarly, copy remaining right sub-array elements.
19	arr[k++] = right[j++];	Copy remaining elements to array.
20	void mergeSort(vector<int>& arr, int low, int high) {…}	Define mergeSort function for recursion.
21	if (low < high) {…}	Initiate sorting if more than one element in sub-array.
22	int mid = low + (high – low) / 2;	Calculate middle index for division.
23	mergeSort(arr, low, mid);	Recursively sort left sub-array.
24	mergeSort(arr, mid + 1, high);	Similarly, sort right sub-array.
25	merge(arr, low, mid, high);	Combine and sort sub-arrays.
26	int main() {…}	Conclude with main function to test Merge Sort.
27	vector<int> arr = {…};	Initialize array for testing.
28	int n = arr.size();	Get size of the array.
29	mergeSort(arr, 0, n – 1);	Apply Merge Sort function to array.
30	cout << “Sorted array: “; {…}	Finally, Display the sorted array.

Complexity Analysis

Time Complexity:

• Worst-case time complexity: O(n log n)
• Average-case time complexity: O(n log n)
• Best-case time complexity: O(n log n)

Space Complexity:

• Auxiliary space complexity: O(n)

In conclusion, merge sort emerges as a potent sorting solution, adept at handling substantial datasets while preserving stability. Furthermore, Its division, sorting, and merging steps epitomize the elegance of divide-and-conquer strategies, delivering consistent and efficient sorting across a variety of scenarios. Hence, understanding merge sort enriches insights into algorithmic complexities and efficient data organization.

Moreover, Quick Sort also uses the same divide and conquer technique for sorting.

Read More about Quick sort.