Problem of the Day: Pyramid Sort

I’ve been sitting on this one for a while but I think it’s time. The idea is simple: sort the numbers so it looks like a pyramid: smaller numbers on the outside and alternating sides, the largest number in the middle.

Working with odd-numbered arrays seems the only way to make it work but any positive number should behave the same when sorting. I’m going to keep two markers, one for the left side and one for the right, that are going to keep moving inward as the array is sorted. Big-O notation is going to be slow since my initial idea is going to move through the array once per value in the array: 5 values needs 5 runs through the array. O(n^n)

The design is for a psort() class to do the work and a main() to send appropriate arrays to it. Someday I’ll have to learn how to use JUnit testing (in Java) to ensure it behaves as expected but for now I’ll do the hard way.

Pyramid Sort

The pyramids of Egypt are some of the most fascinating structures in the world. To honor the great pyramids we’ll be introducing pyramid sort. Pyramid sort works so that the highest numbers are in the center of the array and the lowest are on the edges. When comparing 2 numbers the smaller number goes on the left. So if the array contains 1,2,3 then 1 goes on the left with 2 on the far right and 3 in the middle.

Here are 2 more examples:

> psort([1,2,3,4,5])

> psort([1,3,5,7,9,11])