Definition: The part of a group of data by which it is sorted, indexed, cross referenced, etc.
Note: For instance, to sort customer records alphabetically, the key is the last name, then the given names. Other information, such as the address, outstanding balance, credit limit, etc. do not matter in sorting the records alphabetically. Different keys may be used at different times, for instance, an accounting report may need customers with larger balances first, so the records could be sorted using the outstanding balance as the key.
A 2-pass sort
algorithm that is efficient when the range of keys
is approximately equal to the number of items and only keys are sorted. [...]
More formally, the algorithm is efficient if the range of key is O(number of items), that is, less than or equal to the number of items, with a possible constant multiplier.