Double-Ended Heap-Based Min-Max Sorting Algorithm: A Novel Approach for Efficient Dual-End Placement Sorting

Abstract Sorting is a fundamental operation in computer science that plays a critical role in data organization, retrieval, and computational efficiency. While numerous algorithms such as QuickSort, MergeSort, and HeapSort exist, ongoing research into optimized sorting strategies remains essential to balance time and space complexity for diverse applications. The primary objective of this study is to propose and analyze a new Heap-Based Double-Ended Min-Max Sorting Algorithm that leverages both min-heaps and max-heaps to improve efficiency in dual-ended element extraction. The algorithm was designed and tested on arrays of varying sizes, with performance evaluated in terms of time complexity, space complexity, and comparative efficiency. Results indicate that the algorithm consistently achieves O(n log n) time complexity and requires ⌈n/2⌉ passes by simultaneously placing minimum and maximum elements, thereby improving efficiency compared to traditional quadratic-time algorithms. However, the current design requires O(n) auxiliary space due to the use of two heaps. This research highlights the algorithm’s potential for practical applications in scenarios requiring efficient dual-ended ordering, such as scheduling, simulation, and priority-based systems. Future work may focus on optimizing the method to operate in-place, reducing memory overhead, and exploring parallelization for large-scale datasets.