Merge sort c++ algorithm
Merge sort c++ string
Given a character string in small letter case. Write a C++ function to sort the string using Merge Sort Algorithm.
Merge sort c++ implementation
Merge sort is a popular sorting algorithm that runs in O(nlogn). It uses divide and concur technique so it keeps dividing the input array into two halves while recursively calling the algorithm on those smaller arrays. At the end the algorithm produces two sorted arrays that need to be merged in order to get the final sorted array. The merge part runs in linear time. We only go through the sorted halves and compare one character from the first half to another character in the other half. We push the smaller character to the final result. At the end we push those characters that were not pushed from either half to the final result. Note that in order for the algorithm to operate on the two halves extra space is allocated for each half.
Merge sort c++ step by step
Here is an example. Let us assume the input string is “dcba”
|
1 2 3 4 5 6 |
Split: dcba -> dc : ba Split: dc -> d : c Merge: d : c -> cd Split: ba -> b : a Merge: b : a -> ab Merge: cd : ab -> abcd |
Here is how the merge of cd and ab works:
|
1 2 3 4 |
c > a : push a : result = a merge cd : b c > b : push b : result = ab we are only left with cd so we push cd to the result we get abcd |
Merge sort c++ sample source code
Here is a merge sort c++ program code example
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
//Includes #include <iostream> using namespace std; //Merge sort c++ code explanation //Receives input string and size char* MergeSort(char* str, int n) { //If the string is only one //character then it is already //sorted if (n == 1) { return str; } else { //Calculate the middle int m = n/2; //Allocate space for the two halves char* a = new char[m]; char* b = new char[n-m]; //Copy the first half of the string to a //and the second half of the string to b for (int i = 0; i < m; i++) a[i] = str[i]; for (int i = m; i < n; i++) b[i-m] = str[i]; //Merge sort c++ recursive: //Recursively call the function on the two //halves a = MergeSort(a, m); b = MergeSort(b, n-m); //The rest of the code is to merge the sorted //halves int l = 0; int r = 0; int k = 0; while (l < m && r < n-m) { //If the character from the first half //is less than the character of the //second half then push it to the result if (a[l] <= b[r]) { str[k] = a[l]; l++; } //Otherwise push the character from the //second half else { str[k] = b[r]; r++; } k++; } //If the loop above is finished and still //l is less than m then this means there //are characters in the first half that //need to be appended to the result if (l < m) { while (l < m) { str[k] = a[l]; l++; k++; } } //Similarly we need to append those characters //in the second half that were not added if (r < n-m) { while( r < n-m) { str[k] = b[r]; r++; k++; } } //Return the sorted string return str; } } //Main function void main() { //Sample string char str[] = "dcba"; //Sort string char* res = MergeSort(str, 4); //Print result cout << res << endl; } |
I hope you liked this short merge sort c++ tutorial. If you have questions, please use the comments section below. thanks for reading.
About Author
Mohammed Abualrob
Software Engineer @ Cisco