About lasagne, splitting methods and your favourite film
The ‘Divide and Conquer’-principle was already used in the Roman foreign policy. The politicians and warlords of the ancient world noticed that a large group of people can be easier controlled or even conquered if you split them up into several smaller groups.
Quicksort algorithm: source
CC BY-SA3.0 Roland H.
Luckily the ancient times are long gone, but the principle remains, in particular in computer science. Many algorithms are based on the idea of splitting a task into several easy-to-handle parts. After solving these simpler parts, the solution of the full problem needs to be reconstructed from the solutions of these subproblems. So, it is possible to ‘conquer’ a complex task.
A famous example is the well-known Quicksort algorithm to sort a list of numbers. You start by picking one number in the list (the pivot element) and compare it to every other number of the list. If the other number is smaller, we put it on the left side of our pivot element, if it is larger, we put it on the right side. Thus, we get two sublists, one with smaller and one with larger numbers than the pivot element. We continue to sort these sublists in the same way with new pivot numbers from the sublists. The complete list is sorted when all sublists are sorted.
You may wonder what this is all about and how this is related to our CRC?
