Visual C++ - Sorting Algorithm - Merge Sort Recursive
We often using sorting algorithm to sort numbers and strings. Also we have many sorting algorithms. I have explained here on how merge sort algorithm works.
The recusrive approach requires creatiion multi branch recursion until the elements are comparable by one iterm. The the merging happens with DoMerge function by taking three arguments - start, mid and right.
Click here for C++ Bubble Sort Algorithm
Click here for C++ insertion Sort Algorithm
Click here for C++ Merge Sort Recursive Algorithm
Click here for C++ Merge Sort Iterative Algorithm
Click here for C++ Quick Sort Recursive Algorithm
Click here for C++ Quick Sort Iterative Algorithm
The complete program and test run output are given below:
Source Code
#include <iostream>
#include <string>
void DoMerge(int numbers[], int left, int mid, int right)
{
int temp[25];
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while (left <= left_end)
temp[tmp_pos++] = numbers[left++];
while (mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i=0; i < num_elements; i++)
numbers[right--] = temp[right];
}
void MergeSort(int numbers[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
MergeSort(numbers, left, mid);
MergeSort(numbers, (mid+1), right);
DoMerge(numbers, left, (mid+1), right);
}
}
void MergeSortHelper(int numbers[], int array_size)
{
MergeSort(numbers, 0, array_size - 1);
}
void max()
{
int max;
std::cout << "\nProgram for Ascending order of Numeric Values using MERGE SORT";
std::cout << "\n\nEnter the total number of elements: ";
std::cin >> max;
int *numarray = new int[max];
for(int i = 0; i < max; i++)
{
std::cout << "\nEnter [" << i + 1 << "] element: ";
std::cin >> numarray[i];
}
std::cout << "Before Sorting : ";
for(int k = 0; k < max; k++)
std::cout << numarray[k] << " ";
std::cout << "\n";
MergeSortHelper(numarray,max);
std::cout << "\n\nThe numbers in ascending orders are given below:\n\n";
for(int i = 0; i < max; i++)
{
std::cout << "Sorted [" << i + 1 << "] element: ";
std::cout << numarray[i];
std::cout << "\n";
}
delete [] numarray;
}
Output
Program for Ascending order of Numeric Values using MERGE SORT
Enter the total number of elements: 8
Enter [1] element: 80
Enter [2] element: 60
Enter [3] element: 40
Enter [4] element: 20
Enter [5] element: 10
Enter [6] element: 30
Enter [7] element: 50
Enter [8] element: 70
The numbers in ascending orders are given below:
Sorted [1] element: 10
Sorted [2] element: 20
Sorted [3] element: 30
Sorted [4] element: 40
Sorted [5] element: 50
Sorted [6] element: 60
Sorted [7] element: 70
Sorted [8] element: 80
|
|