Median cut is an algorithm to sort data of an arbitrary number of dimensions into series of sets by recursively cutting each set of data at the median point along the longest dimension.
[1] Suppose we have an image with an arbitrary number of pixels and want to generate a palette of 16 colors.
Put all the pixels of the image (that is, their RGB values) in a bucket.
Find out which color channel (red, green, or blue) among the pixels in the bucket has the greatest range, then sort the pixels according to that channel's values.
This process can be repeated to further subdivide the set of pixels: choose a bucket to divide (e.g., the bucket with the greatest range in any color channel) and divide it into two.