Editing Sorting network (section)

=== Insertion and Bubble networks ===
We can easily construct a network of any size recursively using the principles of insertion and selection. Assuming we have a sorting network of size ''n'', we can construct a network of size {{nowrap|''n'' + 1}} by "inserting" an additional number into the already sorted subnet (using the principle underlying [[insertion sort]]). We can also accomplish the same thing by first "selecting" the lowest value from the inputs and then sort the remaining values recursively (using the principle underlying [[bubble sort]]).[[File:Recursive-bubble-sorting-network.svg|200px|thumb|A sorting network constructed recursively that first sinks the largest value to the bottom and then sorts the remaining wires. Based on [[bubble sort]]]]
{|
| style="vertical-align: top;" |
| style="vertical-align: top;" |[[File:Recursive-insertion-sorting-network.svg|200px|thumb|A sorting network constructed recursively that first sorts the first n wires, and then inserts the remaining value. Based on [[insertion sort]]]]
|}The structure of these two sorting networks are very similar. A construction of the two different variants, which collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.<ref name="knuth"/> 
{|
|style="vertical-align: top;"| [[File:Six-wire-bubble-sorting-network.svg|200px|thumb|Bubble sorting network]]
|style="vertical-align: top;"| [[File:Six-wire-insertion-sorting-network.svg|200px|thumb|Insertion sorting network]]
|style="vertical-align: top;"| [[File:Six-wire-pyramid-sorting-network.svg|200px|thumb|When allowing for parallel comparators, bubble sort and insertion sort are identical]]
|}

The insertion network (or equivalently, bubble network) has a depth of {{math|2''n'' - 3}},<ref name="knuth"/> where {{math|''n''}} is the number of values. This is better than the {{math|''O''(''n'' log ''n'')}} time needed by [[random-access machine]]s, but it turns out that there are much more efficient sorting networks with a depth of just {{math|''O''(log<sup>2</sup> ''n'')}}, as described [[#Constructing sorting networks|below]].