A NEW SORTING METHOD BY TWICE GRADING AND LINKING

A new sorting method of twice grading and linking is presented in this paper. Its algorithm description, time complexity, space complexity, and experimental results in C are given. The algorithmic analysis and experimental results show that the time complexity of this method is O（N） and it has nothing to do with data distribution. Additional memory cost is only N +Δ M +2 when the original data has the character of O（ Δ M ）≤ O（N） （here, N is the amount of original data,Δ M is the change scope of the key）.