To search, Click below search items.


All Published Papers Search Service


An Efficient Sorting Algorithm by Computing Randomized Sorted Sub-Sequences Based on Dynamic Programming


Toqeer Ehsan, M. Usman Ali, Meer Qaisar Javed


Vol. 13  No. 9  pp. 51-57


A lot of sorting algorithms exist today which are based on different problem solving techniques and with different performance behaviors. Algorithms are judged by the running time and space complexity which they take to solve any specific problem. In this papers an efficient sorting algorithm has been introduced, this algorithm is based on dynamic programming technique which is used to solve the optimization problems and here to sort arrays with optimal merges. Algorithm uses a bottom-up approach to compute the pre-sorted sub-sequences of random lengths in a given array of numbers and then sorts the whole array after efficiently combining the identified sub-sequences by using dynamic programming technique. Overlapping sub-problems are identified while sorting the given array and dynamic programming keeps the track of all the overlapping sub-problems by memorizing the data in a tabular form which is the main theme of the mentioned technique. Running time of the algorithm is compared with the standard merge sort and the results are satisfying.


Asymptotic, Complexity, Dynamic programming, Sorted sub-sequence