A New Efficient Algorithm For Internal Sorting

In this paper,a new internal sorting algorithm is presented which is especially suited for sorting record set in which the total number of key values is much smaller than that of records Viz.many records have the same value. If we assume the total number of records to be sorted is N and the total number of key values is M,the sorting efficiency-the total number of comparisons-of classical algorithms (e. g. quicksort,heapsort) is O(N·log₂N), unrelated to M. Under the same assumption,the sorting efficiency of the new algorithm presented in this paper that uses one kind of queue with single pointer data structure, through two passes, is 2·N·log₂M.If some conditioing are added,only one pass is needed and the efficiency is N·log₂M.The moving total number of the new algorithm is N·M/4,and the extra memory space required is M,pointers and M key value locations.