Virtual Radix Counting Bucket sort
정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과, Sang-Un Lee · 한국인터넷방송통신학회 논문지 · 2015
Generally, there is no sorting algorithm much faster than O(nlogn). The quicksort has a best performance O(nlogn) in best and average-case, and in worst-case. This paper suggests virtual radix counting bucket sort such that counting the frequency of numbers in each radix digit, and moves the arbitrary number to proper virtual bucket in the array, and divides the array into radix digit numbers virtually. Also, this algorithm moves the data to proper location within an array for using the minimum auxiliary memory. This algorithm performs k-times such that the number of k digits in given data and the time complexity is O(n). Therefore, this algorithm has a O(kn) time complexity.