Page 226 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

We do the same thing or the other list, 44, 17, 99, and after merging the sorted list will be: 17, Notes
44, 99.
The final two sub-lists are merged in the same way: 32 is compared to 17, so the latter comes first:
17 * * * * * *. Next, 32 is compared to 44, and is smaller so it ends up looking like this : 17 32 * * *
* *. This continues, and in the end the list will be sorted.

Now let us see the implementation of merge sort in c:
#include < iostream >
using namespace std;
void Merge(int *a, int low, int mid, int high)
{
int i = low, j = mid + 1, k = low;
int b[100];
while ((i <= mid) && (j <= high))
{
if (a[i] < a[j])
{
b[k] = a[i];
i++;
}
else
{
b[k] = a[j];
j++;
}
k++;
}
while (i <= mid)
{
b[k] = a[i];
i++;
k++;
}
while (j <= high)
{
b[k] = a[j];
j++;
k++;
}
for (k = low; k <= high; k++)
a[k] = b[k];
}
void MergeSort(int *a, int low, int high)
{
int mid;

LOVELY PROFESSIONAL UNIVERSITY 219