The growing-tree sorting algorithm

In this paper, a new sorting algorithm called the Growing-Tree Sorting Algorithm (GTSA) is proposed to sort a vector of items in a linear time. It implements a structured tree that stores the digits of each input integer and retrieves the integers in the correct order. If d is the maximum number of digits per input number and n is the input size, then it can be shown that the GTSA algorithm requires θ(dn) time to sort both in its best and worst-case scenarios. It can be also shown that the best-case memory complexity of GTSA is θ(d) and that the worst-case memory complexity is θ(dn). To evaluate the performance of GTSA, it was compared with the radix and counting sort algorithms in terms of the memory they consume and their corresponding execution times. The experiments showed that GTSA was, in general, more memory-conservative than counting sort and radix sorting algorithms. The experiments also showed that the GTSA was faster than the radix and counting sort algorithms when the input size was relatively large and the input range was relatively small.