Lazy Merge Sort: An Improvement over Merge Sort

Arrangement of elements in a dataset often forms a crucial aspect in determining the overall performance of the underlying algorithms. Elements arranged in sorted order, either ascending or descending, may serve as an additional benefit for many other algorithms to work upon efficiently. Many algorithms exist in the literature for sorting of the data. The algorithms have wide range of applicability depending on their distinctive properties. However, O(nlogn) algorithms are frequently used in most of the real-world languages and applications. This research aims to further optimize the already existing Merge Sort. It proposes a modified approach named as Lazy Merge Sort that works on the principle of deferred merging until the last step by creating in-between sorted sub-arrays. The proposed approach is further validated and analysed over O(nlogn) baseline algorithms. During the experimentation and validation phase, the proposed Lazy Merge Sort performed better as well as proved to be efficient with respect to other baseline algorithms. The average and worst time complexity for the proposed algorithm is O(nlogn) and traditional Merge Sort serves as an upper bound for it. It offers a competitive alternative to conventional methods and contributes significantly to sorting algorithms in Computer Science.