Performance Evaluation of Lazy-Funnelsort Algorithm on Multicore System - Ahmed, Riaz; Sharma, Lalitsen (International Journal of Computer Sciences and Engineering, 2025)
Sorting is one of the basic problems that have been extensively studied. There are many sorting algorithms which are efficient in computation but cannot use cache efficiently. Efficient use of cache is an important factor for determining the performance of an algorithm. Cache-oblivious algorithms are designed that are both work and cache efficient. The aim of this paper is to evaluate the performance of cache-oblivious sorting algorithm called Lazy Funnelsort on multicore processors. The evaluation is made against the well known fast sorting algorithms: quick sort, merge sort on multicore processor machine. The experiments are conducted against different input sizes and number of processing cores and threads using Intel Cilk Plus, which is extension to C and C++ to express task and data parallelism. The performance of algorithms is examined in terms of execution time, speedup, efficiency and scalability. The results show that parallel implementation of Lazy Funnelsort is better than its sequential implementation and also scalable on multiple cores. Though it has been outperformed by quick sort and merges sort algorithms but shows moderate promise as a parallel algorithm.