PARALLELIZATION OF TIM SORT ALGORITHM USING MPI AND CUDA
Siva Thanagaraja, Keshav Shanbhag, B. Ashwath Rao, Shwetha Rai, NGopalakrishna Kini · Journal of Critical Reviews · 2020
Tim Sort is a sorting algorithm developed in 2002 by Tim Peters. It is one of the secure engineered algorithms, and its high-level principle includes the sequence S is divided into monotonic runs (i.e., nonincreasing or non-decreasing subsequence of S), which should be sorted and should be combined pairwise according to some specific rules. To interpret and examine the merging strategy (meaning that the order in which merge and merge runs are performed) of Tim Sort, we have implemented it in MPI and CUDA environment. Finally, it can be seen the difference in the execution time between serial Tim Sort and parallel Tim sort run in O (n log n) time .