Implementation of merge sort in C++

Merge sort is a popular sorting algorithm that employs the divide-and-conquer strategy. It is widely used for its efficiency and consistency in sorting. This algorithm divides the input array into two halves, sorts each half recursively, and then merges them together to produce a sorted array.

#include <iostream>
void merge_array(int array_value[], int left_value, int middle_value, int right_value)
{
	int number_1 = middle_value - left_value + 1;
	int number_2 = right_value - middle_value;
	int L[number_1], R[number_2];
	for (int i = 0; i < number_1; i++)
		L[i] = array_value[left_value + i];
	for (int i = 0; i < number_2; i++)
		R[i] = array_value[middle_value + 1 + i];
	int i_1 = 0, j_1 = 0, k_1 = left_value;
	while (i_1 < number_1 && j_1 < number_2)
	{
		if (L[i_1] <= R[j_1])
		{
			array_value[k_1] = L[i_1];
			i_1++;
		}
		else
		{
			array_value[k_1] = R[j_1];
			j_1++;
		}
		k_1++;
	}
	while (i_1 < number_1)
	{
		array_value[k_1] = L[i_1];
		i_1++;
		k_1++;
	}
	while (j_1 < number_2)
	{
		array_value[k_1] = R[j_1];
		j_1++;
		k_1++;
	}
}
void merge_sort(int array_value[], int left_value, int right_value)
{
	if (left_value >= right_value)
		return;
	int middle_value = left_value + (right_value - left_value) / 2;
	merge_sort(array_value, left_value, middle_value);
	merge_sort(array_value, middle_value + 1, right_value);
	merge_array(array_value, left_value, middle_value, right_value);
}
void print_array(int array_values[], int size_of_array)
{
	for (int i = 0; i < size_of_array; i++)
		std::cout << array_values[i] << " ";
	std::cout << std::endl;
}
int main()
{
	int array_values[] = { 9, 5, 7, 2, 4, 1, 6, 3, 8 };
	int size_of_array = sizeof(array_values) / sizeof(array_values[0]);
	std::cout << "Original array: ";
	print_array(array_values, size_of_array);
	merge_sort(array_values, 0, size_of_array - 1);
	std::cout << "Sorted array: ";
	print_array(array_values, size_of_array);
	return 0;
}

Lines 5–6: It calculates the sizes of the two subarrays.
Line 8: It declares two temporary arrays, L and R, to respectively store the elements of the left and right subarrays.
Lines 10–13: These loops copy the elements from the original array arr into the temporary arrays L and R.
Lines 17–31: The while loop verifies the elements of the left and right subarrays and saves them in the original array, array_value, in sorted order.
Lines 33–38: Any leftover elements in the left subarray should be copied to the array_value merged array.
Lines 40–45: Any leftover elements in the right subarray should be copied to the array_value merged array.
Lines 51–52: If the left_value index is larger than or equal to the right_value index, then the subarray has just one element. Hence, there is nothing to sort, and the method returns.
Lines 54–56: These lines calculate the middle_value middle index and recursively run the merge_sort() function on the left_value and right_value half subarrays .
Line 57: This line uses the merge_array() function to join the array’s two sorted parts.
Lines 60–65: It prints the elements of the array.
Lines 69–79: The main() function sets the size of the array_values input array and its length via the size_of_array. It then prints the original array, sorts it using the merge_sort() function, and then outputs the sorted array.

Implementation of merge sort in C++

Time complexity

Code

Code explanation