Merge
sort (External sort)
In external sorting process, some
part of the data is held in primary memory during the sorting process and the
remaining data is in secondary storage devices that does not fit in primary
memory. In general, external sorting techniques are used to handle large volume
of data. One of the most important external sorting technique is merge sort.
Merging
ordered files:
A merge is the process that
combines two sorted files data into a single sorted file.
Example:
Here,
File-1 and File-2 are to be merged into File-3. For this, compare the first
value in file-1 with the first value in file-2. Write smaller value 2 into the file-3. Now compare the first value
of file-1 with the second value of file-2. Write the smaller value 3 into file-3
and so on. Finally, file-3 is the output file in which all elements are
available in sorted order.
Merging
un-ordered files:
Ø Merge
sort is a sorting technique designed based on Divide-and-Conquer strategy.
Ø First,
divide the array elements into two sub arrays based on
o
mid=(low+high)/2
Ø Where,
low is the first index and high is the last index of the array.
Ø Now,
these two sub arrays are individually sorted and the resulting sub sequences
are merged to produce a single sorted sequence of data elements.
Ø Here,
Divide-and-Conquer strategy is applicable as splitting the array into two sub
arrays, and combining operation is merging the two sub arrays into single
sorted array.
Example:
0 comments:
Post a Comment