Lesson plan
Pairwise sorting network
The pairwise sorting network is a sorting network discovered and published by Ian Parberry in 1992 in Parallel Processing Letters. The pairwise sorting network has the same size (number of comparators) and depth as the odd–even mergesort network. At the time of publication, the network was one of several known networks with a depth of O(\log^2 n) . It requires n(\log n)(\log n - 1)/4 + n - 1 comparators and has depth (\log n)(\log n + 1)/2 . The sorting procedure implemented by the network is as follows (guided by the zero-one principle): # Sort consecutive pairwise bits of the input (corresponds to the first layer of the diagram) # Sort all pairs into lexicographic order by recursively sorting all odd bits and even bits separately (corresponds to the next three layers of 2+4+8 columns of the diagram) # Sort the pairs in nondecreasing order using a specialized network (corresponds to the final layers of the diagram)
Article summary
The pairwise sorting network is a sorting network discovered and published by Ian Parberry in 1992 in Parallel Processing Letters. The pairwise sorting network has the same size (number of comparators) and depth as the odd–even mergesort network. At the time of publication, the network was one of several known networks with a depth of O(\log^2 n) . It requires n(\log n)(\log n - 1)/4 + n - 1 comparators and has depth (\log n)(\log n + 1)/2 . The sorting procedure implemented by the network is as follows (guided by the zero-one principle): # Sort consecutive pairwise bits of the input (corresponds to the first layer of the diagram) # Sort all pairs into lexicographic order by recursively sorting all odd bits and even bits separately (corresponds to the next three layers of 2+4+8 columns of the diagram) # Sort the pairs in nondecreasing order using a specialized network (corresponds to the final layers of the diagram)
Key claims
- publication date: 1992 — source: Wikipedia · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "1992". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia https://en.wikipedia.org/w/index.php?oldid=1313822723
Key claims and bibliography are generated from the same tracked claims and sources as the article page.