Specializing in programming tutorials that make sense!

You are in Section 7 of 9, Article 7.3 of 7.5

7 .. Sorting Array Data
       7.3 .. Merge Sort

Merge Sort

A merge sort can be used to combine two previously sorted arrays into a third array. The third array will remain sorted.

A merge sort requires two arrays that have been previously sorted into ascending or descending order. When the sort first begins (for ascending order), the first elements of each of the arrays are evaluated to see which array contains the smaller value. Once the smaller value is found, it will be placed as the first element in the third array.

The sort continues to evaluate the elements of both arrays until the end of one of the arrays is reached. Depending on which array has been completely searched, the remaining values in the other array will be attached to the end of the third array.

Algorithm Illustration:

Assume we have the following two integer arrays:

Array 1 1 5 11 22 35 41 52

Array 2 3 4 15 25 46

Here are the results after the first comparison:

Array 1 1 5 11 22 35 41 52

Array 2 3 4 15 25 46

Array 3 1

After the second comparison:

Array 1 1 5 11 22 35 41 52

Array 2 3 4 15 25 46

Array 3 1 3

After the third comparison:

Array 1 1 5 11 22 35 41 52

Array 2 3 4 15 25 46

Array 3 1 3 4

This process is repeated until all elements in both arrays have been placed into the third array.

Example: Merging Into Ascending Order

The following is a complete program demonstrating the merge sort algorithm to merge two arrays previously sorted into ascending order.

It makes use of the following mergeSort function:

// performs merge sorting technique to // combine two one-dimensional arrays // defined for ascending order void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int* size3) { int pos1 = 0; int pos2 = 0; int pos3 = 0; while (pos1 < size1 && pos2 < size2) if (arr1[pos1] < arr2[pos2]) arr3[pos3++] = arr1[pos1++]; else arr3[pos3++] = arr2[pos2++]; if (pos1 < size1) while (pos1 < size1) arr3[pos3++] = arr1[pos1++]; else while (pos2 < size2) arr3[pos3++] = arr2[pos2++]; *size3 = size1 + size2; }

Study the complete program:

arrmergesorta.cpp

Example: Merging Into Descending Order

The following complete program demonstrates how to merge two arrays previously sorted into descending order:

arrmergesortd.cpp

The following complete program demonstrates how to merge two arrays previously sorted into ascending order. The values of both arrays are specified by the user at run-time, a sort routine is executed on each array, and then a merge routine will be executed to merge the two arrays.

arrmergesortuser.cpp

At this point, we've covered the selection, bubble, and merge sort. Sometimes, an array may need to appear sorted when it is actually not. Is this possible?

A standard technique for solving this type of problem is called the tag sort.

Read on for more...

Next: Tag Sort

You are in Section 7 of 9, Article 7.3 of 7.5

[Back to Top]

.: Report Bug : Error Log : About Webmaster :.