Multithreaded Merge Sort

Merge-Sort : The Serial Version
We have
Merge − Sort (A, p, r)
Observation: Sort elements in A [p...r]
1. if (p < r) then
2. q = (p+r)/2
3. Merge − Sort (A, p, q)
4. Merge − Sort (A, q + 1, r)
5. Merge (A, p, q, r)

Merge-Sort : The Parallel Version
We have
Merge − Sort (A, p, r)
Observation: Sort elements in A [p...r]
1. if (p < r) then
2. q = (p+r)/2
3. spawn Merge − Sort (A, p, q)
4. Merge − Sort (A, q + 1, r) // Not necessary to spawn this
5. sync
6. Merge (A, p, q, r)

Comments

Post a Comment

Popular posts from this blog

Fibonacci Heap

Image
Fibonacci Heap . 1) Find Min: Θ(1) [Same as both Binary and Binomial] 2) Delete Min: O(Log n) [Θ(Log n) in both Binary and Binomial] 3) Insert: Θ(1) [Θ(Log n) in Binary and Θ(1) in Binomial] 4) Decrease-Key: Θ(1) [Θ(Log n) in both Binary and Binomial] 5) Merge: Θ(1) [Θ(m Log n) or Θ(m+n) in Binary and Θ(Log n) in Binomial] Like  Binomial Heap , Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). Below is an example Fibonacci Heap taken from  here . Fibonacci Heap maintains a pointer to minimum value (which is root of a tree). All tree roots are connected using circular doubly linked list, so all of them can be accessed using single ‘min’ pointer. The main idea is to execute operations in “lazy” way. For example merge operati
Read more

Amortized analysis- Splay Tree

A splay tree is an efficient implementation of binary search trees that takes advantage of locality in the incoming lookup requests. Locality in this context is a tendency to look for the same element multiple times. A stream of requests exhibits no locality if every element is equally likely to be accessed at each point. For many applications, there is locality, and elements tend to be accessed repeatedly. A good example of an application with this property is a network router. Routers must decide on which outgoing wire to route the incoming packets, based on the IP address in the packets. The router needs a big table (a map) that can be used to look up an IP address and find out which outgoing connection to use. If an IP address has been used once, it is likely to be used again, perhaps many times. Splay trees are designed to provide good performance in this situation. In addition, splay trees offer amortized O(lg n) performance. That is, a sequence of M operations on an n-node s
Read more