Parallel Algorithms: Difference between revisions

Parallel Algorithms (view source)

438 bytes added , 11 February 2020

5,337

edits

@@ Line 136: / Line 136: @@
 ===Techinque: Divide and Conquer===
+;Merge Sort
+Input: Array A[1..n]<br>
+Complexity:<br>
+Time: <math>T(n) \leq T(n/2) + \alpha \log n</math><br>
+Work: <math>T(n) \leq 2 * T(n/2) + \beta n</math><br>
+Time <math>O(\log^2 n)</math>. Work: <math>O(n \log n)</math>
+<pre>
+MergeSort(A, B):
+  if n == 1
+    return B(1) = A(1)
+  call in parallel:
+    MergeSort(A[1:n/2], C[1:n/2])
+    MergeSort(A[n/2+1:n], C[n/2+1:n])
+  Merge C[1:n/2] and C[n/2:n] using O(log n) algorithm
+</pre>
 ==Resources==