Can someone give a real world example for the divide and conquer method? For example, I've heard the boomerang used to explain the idea of a loop back address. What is a real world example we can use to teach students about the divide and conquer method before going to more complex algorithms?
Back around 1985, Susan Merritt created an Inverted Taxonomy of Sorting Algorithms. The idea is that to sort an array you have two phases, the split phase and the join phase. She divided the various algorithms into two types easy split/hard join and hard split/easy join varieties. Merge sort is of the former type. Quick sort is the latter.
But all sorts, envisioned in this way are divide and conquer. Her original paper (part of her doctoral work) is a wonder and worth exploring by any CS teacher.
The simplest example that still bears enough complexity to show what's going on is probably merge sort. It's no coincidence that this algorithm is the classical example to begin explaining the divide and conquer technique.
I am not sure at what level you teach, but your students should be comfortable with both recursion and inductive proofs before venturing far into this territory.
Coincidentally, there is a list of divide and conquer algorithms found here. It's a pretty long list, and might have cast too wide a net. I'm not convinced that I agree that all of the algorithms are genuinely divide and conquer. However, it could be that upon closer inspection, they are.
In any case, it's a great starting point to find algorithms to present to your students. Just be sure that you can clearly explain the central divide/conquer/combine throughline for any algorithms you choose to bring to your students. This area of algorithms is full of traps for unwary beginners, so your students will benefit greatly from thought and care put into your presentation.
These sorts of patterns are a bit tricky in real life. In nice easy computer-science land, every step is the same, just smaller. Merge sort is clearly the ultimate easy example of this.
In real life, we tend to break things up along useful lines. If we're sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together. When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that. In war, we divide an opponent into pieces which cannot work as a cohesive unit, then crush them.
We see this in real life more often than blind divisions because we, as humans, know we can divide along useful lines. The closest I know of that is quicksort's attempt to find a middle index to partition with.
One thing I find tricky about these divide and conquer algorithms is that they look like an infinite regression. You keep proving you can sort lists as long as you can sort smaller lists.... which you know you can do because you can sort smaller lists... so on and so forth. Infinite regression is a serious faux pas in modern logic, so I think people may get confused by that. Showing that "if I can sort a list of length n, I can sort a list of length 2n" would be the more traditional mathematical induction approach.
Then again, all may be for naught, for it is quite clear the best use for divide an conquer in real life is to put together a thrilling Hungarian dance.
If you want to divide a long loaf of bread in 8 or 16 equal pieces, generally people cut it into two equal halves first and then cut each half into two equal halves again, repeating the process until you get as many pieces as you want - 8, 16, 32, or whatever. Almost nobody tries to divide the loaf into 8 pieces all at once - people can guess halves much better than eighths.
We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.