Diamond Sort

Introduction

Diamond sort is a sorting algorithm based on Jared Diamond's popular book on geographical anthropology Guns, Germs, and Steel.

Algorithm Description

For each number in the list to be sorted, create a population of human hunter-gatherers and place them in a region with a number of domesticable animal and plant species proportional to the number. Allow the societies to invent agriculture, civilisation, and industry. The first society to invent guns corresponds to the largest number in the list, at which point the rest of the numbers quickly become irrelevant.

Analysis

This algorithm requires a time to run dependent only on the size of the largest number. It is effectively constant as a function of the number of numbers to be sorted, making it O(1) - a very efficient sorting algorithm indeed. Unfortunately, the constant time required is of the order of 13,000 years, although this can be reduced somewhat by making the largest number to be sorted bigger.