Min Max Merge: A Novel Comparison based Sorting Technique for Data-Intensive Processing

Abstract

Sorting is significant as it is a prerequisite for many applications and functions. It is one of the oldest topics in literature which is still as important as it was in the beginning. Researchers are still working to design more efficient sorting methods either by improving existing sorting methods by reducing time complexity, space complexity, comparisons and shift operations or formulating new ones as sorting is very essential for most used applications such as databases for extracting useful information efficiently. This paper presents a novel comparison-based sorting method named as min max merge sort which works by merging groups of numbers into one group. The Proposed sorting algorithm is not only better than some old classical comparison-based sorting algorithms but it also performs better than some latest presented sorting methods. The basic idea behind proposed sorting algorithm is to divide the input array into different groups and then perform their recursive merging on the basis of their maximum and minimum entries, which circumvents unnecessary data shifts and comparisons. The speed of proposed algorithm is comparatively faster than the traditional sorting methods, as it exploits localized minimum and maximum data entries instead of recursively scanning entire input array. This algorithm exploits linear auxiliary space, as it performs in-place operations for combining groups in same array. Space complexity of proposed sorting method is O(n) as it does not require extra memory space.  Performance comparison of proposed method with other sorts shows the superiority of our proposed method.