In this method, a function fn() is applied to each key. The result of this function determines into which of the several sub-files the record is to be placed. The function should have the property that x <= y, fn (x) <= fn (y). Such a function is called order preserving. Thus all of the records in one sub-file will have keys that are less than or equal to the keys of the records in another sub-file. An item is placed into a sub-file in correct sequence by using any sorting method; simple insertion is often used. After all the items of the original file have been placed into sub-files, the sub-files may be concatenated to produce the sorted result.
25 57 48 37 12 92 86 33
Let us create ten sub-files, one for each of the ten possible first digits. Initially, each of these sub-files is empty. Consider an array of pointers f, where f[i] points to the first element in the file whose digit is i. After scanning the first element (i.e., 25), it is placed into the file header by f. Each of the sub-files is maintained as a sorted linked list of the original array elements. After processing each of the elements in the original file, the sub-files appear as in the figure shown below,
Got Something To Say: