Content deleted Content added
Citation bot (talk | contribs) Alter: isbn, template type. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox3 | via #UCB_webform_linked |
|||
Line 15:
== Merging two lists ==
Merging two sorted lists into one can be done in [[linear time]] and linear space. The following [[pseudocode]] demonstrates an algorithm that merges input lists (either [[linked list]]s or [[Array data structure|arrays]]) {{mvar|A}} and {{mvar|B}} into a new list {{mvar|C}}.<ref name="skiena">{{cite book |last=Skiena |first=Steven |authorlink=Steven Skiena |title=The Algorithm Design Manual |publisher=[[Springer Science+Business Media]] |edition=2nd |year=2010 |isbn=978-1-849-96720-
'''algorithm''' merge(A, B) '''is'''
Line 112:
merge(A[r+1...j], B[s...ℓ], C[t+1...q])
The algorithm operates by splitting either {{mvar|A}} or {{mvar|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The [[binary search]] subroutine returns the index in {{mvar|B}} where {{math|''A''[''r'']}} would be, if it were in {{mvar|B}}; that this always a number between {{mvar|k}} and {{mvar|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{
The [[Analysis of parallel algorithms#Overview|work]] performed by the algorithm for two arrays holding a total of {{mvar|n}} elements, i.e., the running time of a serial version of it, is {{math|''O''(''n'')}}. This is optimal since {{mvar|n}} elements need to be copied into {{mvar|C}}. To calculate the [[Analysis of parallel algorithms#Overview|span]] of the algorithm, it is necessary to derive a [[Recurrence relation]]. Since the two recursive calls of ''merge'' are in parallel, only the costlier of the two calls needs to be considered. In the worst case, the maximum number of elements in one of the recursive calls is at most <math display="inline">\frac 3 4 n</math> since the array with more elements is perfectly split in half. Adding the <math>\Theta\left( \log(n)\right)</math> cost of the Binary Search, we obtain this recurrence as an upper bound:
| |||