Mergesort on all the spices in the kitchen

It bothered me that the spices in the kitchen were out of order. So, I sorted them using my favorite sorting algorithm, Mergesort. My cats helped.

I started with an un-ordered list of spices.

Then I started to divide the list up into smaller lists. Panther helped.

31 elements became 15 and 16.

Then 7, 8, 8, 8.

Then 3, 4, 4, 4, 4, 4, 4, 4.

Then 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Then the sorting began. Each two element group, I sorted. Then I treated each one as a queue. For each set of two queues, I dequeued the head element of lowest alphabetical value, and enqueued it into a result queue. I repeated this until there was only one, sorted queue remaining.

Then I put it back into the spice cabinet! When Sabrina asks, “Who got my spices out of order,” I will reply, “I got them in order.”