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.
Home | Esoteric Programming Languages
Last updated: Wednesday, 30 August, 2006; 22:51:51 PDT.
Copyright © 1990-2022, David Morgan-Mar. dmm@dangermouse.net
Hosted by: DreamHost