Worksheet 7
Odd-Even Sort

1. Perform an Odd-Even Sort on the following array, manually.

+---+---+---+---+---+---+---+---+
| 9 | 7 | 2 | 1 | 3 | -1| 8 | 5 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| 9 | 2 | 7 | 1 | 3 | -1| 8 | 5 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| 2 | 9 | 1 | 7 | -1| 3 | 5 | 8 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| 2 | 1 | 9 | -1| 7 | 3 | 5 | 8 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| 1 | 2 | -1| 9 | 3 | 7 | 5 | 8 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| 1 | -1| 2 | 3 | 9 | 5 | 7 | 8 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| -1| 1 | 2 | 3 | 5 | 9 | 7 | 8 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| -1| 1 | 2 | 3 | 5 | 7 | 9 | 8 |
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| -1| 1 | 2 | 3 | 5 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+

2. Divide the following array in half, sort each half, then merge the two halves.

+---+---+---+---+---+---+---+---+
| 9 | 7 | 2 | 1 | 3 | -1| 8 | 5 |
+---+---+---+---+---+---+---+---+

                |
+---+---+---+---+---+---+---+---+
| 1 | 2 | 7 | 9 | -1| 3 | 5 | 8 |
+---+---+---+---+---+---+---+---+
                |

+---+---+---+---+---+---+---+---+
| -1| 1 | 2 | 3 | 5 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+