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.
For example:
An array,
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[10], 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[2]. 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,
Follow Us!