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.

Time complexity

The time complexity of the provided merge sort implementation is O(nlog⁡n)O(n\log n), where nn represents number of the elements in the array.

Code

Code explanation

• 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.