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 , where represents number of the elements in the array.
Code
#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;}
Code explanation
-
Lines 5–6: It calculates the sizes of the two subarrays.
-
Line 8: It declares two temporary arrays,
LandR, to respectively store the elements of the left and right subarrays. -
Lines 10–13: These loops copy the elements from the original array
arrinto the temporary arraysLandR. -
Lines 17–31: The
whileloop 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_valuemerged array. -
Lines 40–45: Any leftover elements in the right subarray should be copied to the
array_valuemerged array. -
Lines 51–52: If the
left_valueindex is larger than or equal to theright_valueindex, 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_valuemiddle index and recursively run themerge_sort()function on theleft_valueandright_valuehalf 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 thearray_valuesinput array and its length via thesize_of_array. It then prints the original array, sorts it using themerge_sort()function, and then outputs the sorted array.
