Quicksort explained to kids
Quicksort's actually pretty easy to understand, if they understand basic counting and division by 2.  Make a bunch of X flash cards, number them 1--X, and shuffle it.  Then here's the explanation:


  OK, we've got this deck of (let's say 20) cards here.  We want to put
  them in order, so 1 is first, then 2, then 3, and so on.  Here's a
  very quick way to do it.
  
  First, let's go through this deck and make two piles out of it.  Half
  of 20 is 10, so anything bigger than 10 goes in this pile on the
  right, and anything smaller goes in this pile on the left.  (Make sure
  to demonstrate as you go.)
  
  Now, let's do the same thing with the smaller piles.  What's half of
  10?  (Someone says "five!") That's right!  So anything bigger than 5
  goes in this pile on the right, and anything smaller goes in this pile
  on the left.
  
  And over here, we've got the group that's bigger than 10.  So half of
  10 is 5, and what's 10 plus 5? (Someone says "fifteen!") That's right!
  So anything bigger than 15 goes in this pile on the right, and
  anything smaller than 15 goes in this pile on the left.
  
  And now the piles are getting small enough that you can easily look at
  them and put them in order.  Look, here we've got 2, 4, 5, 3, 1.  So
  we just switch them around like this, and you can see 1, 2, 3, 4, 5.
  So let's do the same thing with the other piles, and then we just put
  the piles in order, and look!  They're in order from 1 to 20!


Congratulations.  You've just taught a bunch of children the basic principles of an adaptive quicksort algorithm!  You can go a bit deeper than that depending on mental maturity, but going much further beyond this point requires some understanding of formal logic.

As for proving its complexity, that's trickier.  It's one of the things that requires formal logic, and they'll have to understand the basic principles of big-O notation in the first place.  You might want to hold off on that part at first.