Algorithm:
1) Divide the array repeatedly into two halves
2) Stop dividing when there is single element left. By fact, single element is already sorted.
3) Merges two already sorted sub arrays into one.
Example:
The basic merging algorithm takes two input arrays a and b, an output array c. Consider three counters, aptr, bptr, and cptr, which are initially set to the beginning of their respective arrays.The smaller of a[aptr] and b[bptr] is copied to the next entry in c, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the other list is copied to c.
If the array a contains 1, 13, 24, 26, and b contains 2, 15, 27, 38, then the algorithm proceeds as follows: First, a comparison is done between 1 and 2. 1 is added to c, and then 13 and 2 are compared.
2 is added to c, and then 13 and 15 are compared.
13 is added to c, and then 24 and 15 are compared. This proceeds until 26 and 27 are compared.
26 is added to c, and the a array is exhausted.
The remainder of the b array is then copied to c.
The time to merge two sorted lists is clearly linear, because at most n - 1 comparisons are made, where n is the total number of elements.
No comments:
Post a Comment