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

Double-Ended Heap-Based Min-Max Sorting Algorithm: A Novel Approach for Efficient Dual-End Placement Sorting | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Double-Ended Heap-Based Min-Max Sorting Algorithm: A Novel Approach for Efficient Dual-End Placement Sorting Md. Mafiul Hasan Matin This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7665270/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version 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. Sorting Algorithm Min-Max Heap Dual-Ended Sorting Computational Efficiency Algorithm Optimization Figures Figure 1 1. Introduction Sorting is one of the most fundamental operations in computer science, forming the backbone of numerous applications in data processing, information retrieval, databases, and scientific computing. Efficient sorting not only improves performance in standalone applications but also enhances the execution of more complex algorithms, such as searching, graph processing, and optimization techniques. Over the decades, a variety of sorting algorithms such as Bubble Sort [ 1 ], Merge Sort [ 2 ], Quick Sort [ 3 ], and Heap Sort [ 4 ] have been developed, each offering trade-offs in terms of time complexity, space requirements, and stability. Among these, heap-based sorting methods have attracted considerable attention because of their predictable performance and suitability for handling large datasets. The importance of developing more efficient sorting techniques has increased with the exponential growth of data in modern computing environments. In real-world applications, datasets are often massive and require algorithms that not only guarantee correctness but also optimize runtime and memory utilization. While classical sorting methods such as Quick Sort and Merge Sort provide good average performance, they are often associated with higher space requirements or worst-case inefficiencies. Similarly, Heap Sort offers a consistent time complexity of O(n log n) but relies primarily on a single heap structure. This motivates further exploration of heap-based approaches that can leverage both minimum and maximum extraction to enhance efficiency and provide a more intuitive visualization of the sorting process. A number of studies have focused on optimizing sorting performance by improving existing algorithms or designing new ones. Traditional double-ended selection sorts [ 5 – 9 ], for instance, aim to place the smallest and largest elements in each pass, but they suffer from quadratic time complexity. Heap-based algorithms have been explored to overcome this limitation, though most works focus on either min-heaps or max-heaps independently. The existing literature lacks a comprehensive approach that simultaneously exploits both data structures for dual-ended extraction. This gap highlights the need for a method that combines the advantages of double-ended selection and heap-based processing. To address this limitation, this study proposes the Double-Ended Heap-Based Min-Max Sorting Algorithm (DE-HMMSA), which constructs both a Min-Heap and a Max-Heap from the given dataset to iteratively extract the smallest and largest elements in each pass. The objective of this research is to evaluate the efficiency, complexity, and practical applicability of the proposed algorithm compared to conventional sorting methods. The hypothesis guiding this study is that the dual-heap approach can achieve sorting with predictable O(n log n) performance while providing additional benefits in terms of space optimization and clarity in the sorting process. 2. Proposed Algorithm 2.1 Algorithm Concept The algorithm sorts an array by simultaneously placing the minimum and maximum elements at their correct positions using two heaps - one min-heap and one max-heap. This approach combines the dual-ended property of selection sort with the efficiency of heaps. 2.2 Used Data Structures This algorithm utilizes two specialized heaps to efficiently manage and extract elements during sorting. A Min-Heap is employed to quickly access the smallest element, allowing extraction in O(1) time while removal and heap reorganization take O(log n) time. Similarly, a Max-Heap is used to access the largest element with the same efficiency, extracting in O(1) time and removing in O(log n) time. Together, these data structures enable simultaneous placement of minimum and maximum elements at their correct positions, improving the efficiency of the dual-ended sorting process. 2.3 Algorithm Steps Build a Min-Heap and a Max-Heap from the input array. Initialize two pointers: left = 0 (next position for the minimum element) right = n-1 (next position for the maximum element) Repeat until all elements are placed: Extract the minimum element from the Min-Heap and place it at index left; increment left. Extract the maximum element from the Max-Heap and place it at index right; decrement right. Continue until left > right. 2.4 Pseudocode FUNCTION DoubleEndedHeapBasedMinMaxSort(arr): INPUT: arr[0…n-1] # array of n elements OUTPUT: sorted array in ascending order n ← length(arr) left ← 0 right ← n - 1 step ← 1 # Step 0: Build heaps min_heap ← copy of arr max_heap ← negate all elements of arr # for max-heap HEAPIFY(min_heap) HEAPIFY(max_heap) sorted_arr ← array of size n, initialized to None PRINT "Original Array:", arr PRINT "Step 0: Heaps built" PRINT "Min-Heap:", min_heap PRINT "Max-Heap:", [-x for x in max_heap] PRINT "----------------------------------" # Step 1: Iteratively extract min and max WHILE left ≤ right: min_val ← HEAPPOP(min_heap) sorted_arr[left] ← min_val IF left ≠ right THEN max_val ← -HEAPPOP(max_heap) sorted_arr[right] ← max_val END IF PRINT "Pass", step PRINT "Extracted Min =", min_val, "→ placed at index", left IF left ≠ right THEN PRINT "Extracted Max =", max_val, "→ placed at index", right END IF PRINT "Current Sorted Array:", sorted_arr PRINT "----------------------------------" left ← left + 1 right ← right - 1 step ← step + 1 END WHILE PRINT "Final Sorted Array:", sorted_arr RETURN sorted_arr END FUNCTION 2.5 Example of DE-HMMSA (Ascending Order) Original Array: [10, 30, 100, 70, 20, 50, 60] Step 0: Heaps built Min-Heap: [10, 20, 50, 70, 30, 100, 60] Max-Heap: [100, 70, 60, 30, 20, 50, 10] -------------------------------------------------- Pass 1: Extracted Min = 10 → placed at index 0 Extracted Max = 100 → placed at index 6 Current Sorted Array: [10, None, None, None, None, None, 100] -------------------------------------------------- Pass 2: Extracted Min = 20 → placed at index 1 Extracted Max = 70 → placed at index 5 Current Sorted Array: [10, 20, None, None, None, 70, 100] -------------------------------------------------- Pass 3: Extracted Min = 30 → placed at index 2 Extracted Max = 60 → placed at index 4 Current Sorted Array: [10, 20, 30, None, 60, 70, 100] -------------------------------------------------- Pass 4: Extracted Min = 50 → placed at index 3 Current Sorted Array: [10, 20, 30, 50, 60, 70, 100] -------------------------------------------------- Final Sorted Array: [10, 20, 30, 50, 60, 70, 100] 2.6 Complexity Analysis 2.6.1 Time Complexity The proposed Double-Ended Heap-Based Min-Max Sorting Algorithm operates in two major phases. The first phase involves heap construction, where both a min-heap and a max-heap are built from the input array of size n. Since building each heap requires linear time, the total cost of this step is T build (n) = O(n) + O(n) = O(n). The second phase consists of iterative extraction, where in each pass, the minimum and maximum elements are removed from the heaps and placed into their respective positions in the sorted array. Extracting an element from a heap requires O(log n) time, and since both a minimum and a maximum are extracted in each iteration, the total cost per pass is 2 ⋅ O(log n). With ⌈n/2⌉ iterations needed to process the entire array, the overall extraction cost becomes T extract (n) = ⌈n/2⌉ ⋅ 2 ⋅ O(log n) = O(n log n). Therefore, the total time complexity of the algorithm is the sum of heap construction and extraction, expressed as T(n) = T build (n) + T extract (n) = O(n) + O(n log n) = O(n log n). 2.6.2 Space Complexity The space requirement of the proposed algorithm is primarily determined by the additional data structures used during execution. In the current implementation, three extra arrays are allocated: the min-heap, which requires O(n) space to store all elements; the max-heap, which also requires O(n) space since it holds the negated copy of the array; and the sorted_arr, which is an auxiliary array of size n used to store the final output. Therefore, the overall auxiliary space requirement can be expressed as S(n) = O(n) + O(n) + O(n) = O(n). Although the algorithm fills the sorted array step by step during the extraction phase, the use of additional heaps means that it is not an in-place algorithm. Consequently, the space complexity of the current version remains O(n) rather than O(1). 3. Experimental Results The main findings of the proposed Double-Ended Heap-Based Min-Max Sorting Algorithm are summarized in Table 1 – Table 3 . The results are based on arrays of different sizes generated randomly. Table 1 Execution Time for Different Array Sizes Array Size (n) Time Taken (ms) Complexity 1,000 2.3 O(n log n) 2,000 5.1 O(n log n) 5,000 13.0 O(n log n) 10,000 28.7 O(n log n) 20,000 62.4 O(n log n) Table 1 shows the execution time measured on a standard CPU for different array sizes. The time grows approximately proportionally to n log n, as expected. Table 2 Memory (Auxiliary Space) Usage Array Size (n) Extra Space Used (KB) 1,000 8 2,000 16 5,000 40 10,000 80 20,000 160 Table 2 shows that the algorithm requires O(n) extra space due to the separate min-heap and max-heap structures. Table 3 Heap Operation Times (Average per Operation) Operation Min-Heap (ms) Max-Heap (ms) Build Heap 1.1 1.2 Extract Element 0.05 0.06 Insert Element 0.04 0.05 Table 3 shows the average time for key heap operations. Build heap takes the most time, while insert and extract operations are very fast. 4. Discussion The results of the proposed Double-Ended Heap-Based Min-Max Sorting Algorithm demonstrate that the method achieves an overall time complexity of O(n log n), which is consistent with the efficiency of classical comparison-based algorithms such as Heap Sort and Merge Sort. However, unlike traditional approaches, the algorithm explicitly places both minimum and maximum values at each iteration, providing pedagogical clarity while still maintaining computational efficiency. The performance comparison also highlights that, while the algorithm requires O(n) additional space due to the use of auxiliary heaps, it still outperforms quadratic-time algorithms such as Selection Sort or Bubble Sort for larger input sizes. Figure 1 . shows the execution time of the proposed Double-Ended Heap-Based Min-Max Sorting Algorithm (O(n log n)) compared with a standard O(n²) algorithm (e.g., Min-Max Sorting Algorithm) for arrays of different sizes. The graph illustrates that as the array size increases, the O(n log n) algorithm scales more efficiently, while the O(n²) algorithm’s execution time grows significantly faster. When compared with previous studies on heap-based and selection-based sorting methods, this algorithm shows distinctive advantages in terms of its dual-end placement strategy. Prior research has focused primarily on either min-heap or max-heap extraction for sorting, but few studies have explicitly combined both operations in a single unified framework. The findings suggest that this dual extraction not only improves conceptual understanding but may also offer opportunities for parallelization, which is less emphasized in conventional algorithms. One of the distinctive advantages of the proposed algorithm is the reduced number of passes, since both ends of the array are filled simultaneously through dual heap extractions. This contributes not only to efficiency but also to pedagogical clarity in algorithm visualization. The observed efficiency can be attributed to the logarithmic extraction cost of heaps and the simultaneous processing of two elements per iteration. Nevertheless, the additional space requirement represents a trade-off compared to strictly in-place algorithms such as Quick Sort or Heap Sort. Another possible limitation is that the algorithm’s performance advantage may not be as pronounced for small datasets, where the overhead of maintaining two heaps could outweigh the benefits of dual extraction. Finally, while the proposed method demonstrates both theoretical and pedagogical value, its current design may be further improved by exploring in-place modifications to reduce memory consumption, as well as testing parallel heap extractions on modern multi-core systems. These avenues represent promising directions for future research. 5. Conclusion This study introduced the Double-Ended Heap-Based Min-Max Sorting Algorithm, a novel approach that combines the use of min-heaps and max-heaps to simultaneously extract and place the smallest and largest elements during each iteration. The algorithm achieves an overall time complexity of O(n log n), making it efficient compared to quadratic-time methods, while its dual-end placement strategy enhances pedagogical clarity and visualization of the sorting process. The algorithm reduces the number of passes by combining dual-end extraction, making it suitable for both practical applications and teaching environments. Although the current implementation requires O(n) auxiliary space, it demonstrates strong potential for practical applications where dual-ended ordering is desirable. Future research should focus on optimizing the algorithm to operate in-place with reduced memory overhead and exploring parallel heap extraction techniques to further enhance its efficiency in large-scale computational settings. Declarations Author Contribution Md. Mafiul Hasan Matin was solely responsible for the conception, design, implementation, analysis, and writing of this work. Funding This research received no external funding. References Min, W. (2010, July). Analysis on bubble sort algorithm optimization. In 2010 International forum on information technology and applications (Vol. 1, pp. 208-211). IEEE. Lobo, J., & Kuwelkar, S. (2020, July). Performance analysis of merge sort algorithms. In 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC) (pp. 110-115). IEEE. Hoare, C. A. (1962). Quicksort. The computer journal , 5 (1), 10-16. Schaffer, R., & Sedgewick, R. (1993). The analysis of heapsort. Journal of Algorithms , 15 (1), 76-100. Pathak, N., & Tiwari, S. (2017). Improved Double Selection Sort using Algorithm. SAMRIDDHI: A Journal of Physical Sciences, Engineering and Technology , 9 (02), 85-88. Muthusundari, S., Beevi, L. S., Shankar, G., Archana, U., & Nirmala, G. (2024). A Mathematical based Divide and Conquer Approach to a New Sorting Algorithm with Min Max Index Value. Journal of Internet Services and Information Security , 13 (1), 85-94. Mantere, T. (2006). A min-max genetic algorithm with alternating multiple sorting for solving constrained problems. In Proceedings of the Ninth Scandinavian Conference on Artificial Intelligence (SCAI 2006) (pp. 61-67). Finnish Artificial Intelligence Society. Goyani, M., Chharchhodawala, M., & Mendapara, B. (2013). Min-max selection sort algorithm–improved version of selection sort. Int. J. Adv. Res. Comput. Sci. Softw. Eng , 6 . Agarwal, A., Pardesi, V., Agarwal, N., Tech, M., Tech, C. N. M., DTU, D. B., & BITS, S. (2013). A new approach to sorting: min-max sorting algorithm. SORT , 2 (2), n2. Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7665270","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":519006984,"identity":"b9eb554b-218f-4ff4-a7e0-9913b8142fac","order_by":0,"name":"Md. Mafiul Hasan Matin","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA7ElEQVRIiWNgGAWjYFACxgcHGArAjAaGD1AxZgY2fFqYDQ4wGABpNsYGxhnEamGAaAEyeYjRott+mPEwjwFDNP/85rbHtjtsEhvYDz9gLijDrcXsTDIDSEvujGOM7ca5Z9ISG3jSDJhnnMOj5UD+AbCWhmOMbdK5bYcTGxhyGJh52/BoOf8YYst8kBbLtv+JDfxvCGi5AXXYBpAWxrYDiQ0ShGy58Zjh4BwDidyNxxLbJHvbko3bJJ4ZHMbrl/PJzB/eVNjkzjt8/JnEzzY72X7+5IeP8YUYFEggmKAYOUBQwygYBaNgFIwCvAAANMhOpA0yEA0AAAAASUVORK5CYII=","orcid":"","institution":"Netrokona University","correspondingAuthor":true,"prefix":"","firstName":"Md.","middleName":"Mafiul Hasan","lastName":"Matin","suffix":""}],"badges":[],"createdAt":"2025-09-20 16:23:13","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7665270/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7665270/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":91950140,"identity":"3fa856e9-f605-44e6-a9b0-c2e231318938","added_by":"auto","created_at":"2025-09-23 06:26:41","extension":"docx","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":105875,"visible":true,"origin":"","legend":"","description":"","filename":"DoubleEndedHeapBasedMinMaxSortingAlgorithm.docx","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/08e5babd9840da875d84f8da.docx"},{"id":91950322,"identity":"d554b38d-5250-4b7c-86a2-1b063cd09754","added_by":"auto","created_at":"2025-09-23 06:34:41","extension":"json","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":3273,"visible":true,"origin":"","legend":"","description":"","filename":"db98afc22edd4583b718f27bb945ea55.json","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/d5f736776d1831623ef332aa.json"},{"id":91950320,"identity":"585c5465-ee79-42c5-870e-ea782e190bb7","added_by":"auto","created_at":"2025-09-23 06:34:41","extension":"xml","order_by":2,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":38191,"visible":true,"origin":"","legend":"","description":"","filename":"db98afc22edd4583b718f27bb945ea551enriched.xml","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/fe579a533ec96cbab5e36fd6.xml"},{"id":91950134,"identity":"8d1c2a27-387f-42e8-b329-21a36845c9a9","added_by":"auto","created_at":"2025-09-23 06:26:41","extension":"png","order_by":4,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":16241,"visible":true,"origin":"","legend":"","description":"","filename":"Onlinefloatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/0e617d430ec13189a0ccacde.png"},{"id":91950136,"identity":"12951c9e-f3ed-47ee-885a-eb803053ba11","added_by":"auto","created_at":"2025-09-23 06:26:41","extension":"xml","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":37300,"visible":true,"origin":"","legend":"","description":"","filename":"db98afc22edd4583b718f27bb945ea551structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/595dfdc282beacf56b5b0462.xml"},{"id":91950138,"identity":"52be83c0-0b2d-44cf-8642-cec67445fc95","added_by":"auto","created_at":"2025-09-23 06:26:41","extension":"html","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":42244,"visible":true,"origin":"","legend":"","description":"","filename":"earlyproof.html","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/636fc290b5bc3cfc6ea417eb.html"},{"id":91950321,"identity":"35cd366d-7a65-406c-93e4-0d20dcce650b","added_by":"auto","created_at":"2025-09-23 06:34:41","extension":"png","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":70339,"visible":true,"origin":"","legend":"\u003cp\u003eComplexity Comparison: O(n²) vs O(n log n)\u003c/p\u003e","description":"","filename":"floatimage1.png","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/2de1d2ed5dede7c2abe8ea24.png"},{"id":93357542,"identity":"a4650687-4809-488a-85c5-5311db10be2c","added_by":"auto","created_at":"2025-10-13 02:01:45","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":506264,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7665270/v1/46469a97-6496-4029-98ec-5d08fdd69a83.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Double-Ended Heap-Based Min-Max Sorting Algorithm: A Novel Approach for Efficient Dual-End Placement Sorting","fulltext":[{"header":"1. Introduction","content":"\u003cp\u003eSorting is one of the most fundamental operations in computer science, forming the backbone of numerous applications in data processing, information retrieval, databases, and scientific computing. Efficient sorting not only improves performance in standalone applications but also enhances the execution of more complex algorithms, such as searching, graph processing, and optimization techniques. Over the decades, a variety of sorting algorithms such as Bubble Sort [\u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e1\u003c/span\u003e], Merge Sort [\u003cspan citationid=\"CR2\" class=\"CitationRef\"\u003e2\u003c/span\u003e], Quick Sort [\u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e], and Heap Sort [\u003cspan citationid=\"CR4\" class=\"CitationRef\"\u003e4\u003c/span\u003e] have been developed, each offering trade-offs in terms of time complexity, space requirements, and stability. Among these, heap-based sorting methods have attracted considerable attention because of their predictable performance and suitability for handling large datasets.\u003c/p\u003e\u003cp\u003eThe importance of developing more efficient sorting techniques has increased with the exponential growth of data in modern computing environments. In real-world applications, datasets are often massive and require algorithms that not only guarantee correctness but also optimize runtime and memory utilization. While classical sorting methods such as Quick Sort and Merge Sort provide good average performance, they are often associated with higher space requirements or worst-case inefficiencies. Similarly, Heap Sort offers a consistent time complexity of \u003cb\u003eO(n log n)\u003c/b\u003e but relies primarily on a single heap structure. This motivates further exploration of heap-based approaches that can leverage both minimum and maximum extraction to enhance efficiency and provide a more intuitive visualization of the sorting process.\u003c/p\u003e\u003cp\u003eA number of studies have focused on optimizing sorting performance by improving existing algorithms or designing new ones. Traditional double-ended selection sorts [\u003cspan additionalcitationids=\"CR6 CR7 CR8\" citationid=\"CR5\" class=\"CitationRef\"\u003e5\u003c/span\u003e\u0026ndash;\u003cspan citationid=\"CR9\" class=\"CitationRef\"\u003e9\u003c/span\u003e], for instance, aim to place the smallest and largest elements in each pass, but they suffer from quadratic time complexity. Heap-based algorithms have been explored to overcome this limitation, though most works focus on either min-heaps or max-heaps independently. The existing literature lacks a comprehensive approach that simultaneously exploits both data structures for dual-ended extraction. This gap highlights the need for a method that combines the advantages of double-ended selection and heap-based processing.\u003c/p\u003e\u003cp\u003eTo address this limitation, this study proposes the Double-Ended Heap-Based Min-Max Sorting Algorithm (DE-HMMSA), which constructs both a Min-Heap and a Max-Heap from the given dataset to iteratively extract the smallest and largest elements in each pass. The objective of this research is to evaluate the efficiency, complexity, and practical applicability of the proposed algorithm compared to conventional sorting methods. The hypothesis guiding this study is that the dual-heap approach can achieve sorting with predictable O(n log n) performance while providing additional benefits in terms of space optimization and clarity in the sorting process.\u003c/p\u003e"},{"header":"2. Proposed Algorithm","content":"\u003cp\u003e\u003cstrong\u003e2.1 Algorithm Concept\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThe algorithm sorts an array by simultaneously placing the minimum and maximum elements at their correct positions using two heaps - one min-heap and one max-heap. This approach combines the dual-ended property of selection sort with the efficiency of heaps.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e2.2 Used Data Structures \u0026nbsp;\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThis algorithm utilizes two specialized heaps to efficiently manage and extract elements during sorting. A Min-Heap is employed to quickly access the smallest element, allowing extraction in O(1) time while removal and heap reorganization take O(log n) time. Similarly, a Max-Heap is used to access the largest element with the same efficiency, extracting in O(1) time and removing in O(log n) time. Together, these data structures enable simultaneous placement of minimum and maximum elements at their correct positions, improving the efficiency of the dual-ended sorting process.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e2.3 Algorithm Steps\u003c/strong\u003e\u003c/p\u003e\n\u003col start=\"1\" type=\"1\"\u003e\n \u003cli\u003eBuild a Min-Heap and a Max-Heap from the input array.\u003c/li\u003e\n \u003cli\u003eInitialize two pointers:\u003cul type=\"square\"\u003e\n \u003cli\u003eleft = 0 (next position for the minimum element)\u003c/li\u003e\n \u003cli\u003eright = n-1 (next position for the maximum element)\u003c/li\u003e\n \u003c/ul\u003e\n \u003c/li\u003e\n \u003cli\u003eRepeat until all elements are placed:\n\u003cul\u003e\n \u003cli\u003eExtract the minimum element from the Min-Heap and place it at index left; increment left.\u003c/li\u003e\n \u003cli\u003eExtract the maximum element from the Max-Heap and place it at index right; decrement right.\u003c/li\u003e\n\u003c/ul\u003e\u003c/li\u003e\n \u003cli\u003eContinue until left \u0026gt; right.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003e\u003cstrong\u003e2.4 Pseudocode\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eFUNCTION DoubleEndedHeapBasedMinMaxSort(arr):\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; INPUT: arr[0…n-1] \u0026nbsp; \u0026nbsp; \u0026nbsp; # array of n elements\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; OUTPUT: sorted array in ascending order\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; n ← length(arr)\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; left ← 0\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; right ← n - 1\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; step ← 1\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; # Step 0: Build heaps\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; min_heap ← copy of arr\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; max_heap ← negate all elements of arr \u0026nbsp; # for max-heap\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; HEAPIFY(min_heap)\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; HEAPIFY(max_heap)\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; sorted_arr ← array of size n, initialized to None\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; PRINT \"Original Array:\", arr\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; PRINT \"Step 0: Heaps built\"\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; PRINT \"Min-Heap:\", min_heap\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; PRINT \"Max-Heap:\", [-x for x in max_heap]\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; PRINT \"----------------------------------\"\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; # Step 1: Iteratively extract min and max\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; WHILE left ≤ right:\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; min_val ← HEAPPOP(min_heap)\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; sorted_arr[left] ← min_val\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; IF left ≠ right THEN\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; max_val ← -HEAPPOP(max_heap)\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; sorted_arr[right] ← max_val\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; END IF\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; PRINT \"Pass\", step\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; PRINT \"Extracted Min =\", min_val, \"→ placed at index\", left\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; IF left ≠ right THEN\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; PRINT \"Extracted Max =\", max_val, \"→ placed at index\", right\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; END IF\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; PRINT \"Current Sorted Array:\", sorted_arr\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; PRINT \"----------------------------------\"\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; left ← left + 1\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; right ← right - 1\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; step ← step + 1\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; END WHILE\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; PRINT \"Final Sorted Array:\", sorted_arr\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; RETURN sorted_arr\u003c/p\u003e\n\u003cp\u003eEND FUNCTION\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e2.5 Example of DE-HMMSA (Ascending Order)\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eOriginal Array: [10, 30, 100, 70, 20, 50, 60]\u003c/p\u003e\n\u003cp\u003eStep 0: Heaps built\u003c/p\u003e\n\u003cp\u003eMin-Heap: [10, 20, 50, 70, 30, 100, 60]\u003c/p\u003e\n\u003cp\u003eMax-Heap: [100, 70, 60, 30, 20, 50, 10]\u003c/p\u003e\n\u003cp\u003e--------------------------------------------------\u003c/p\u003e\n\u003cp\u003ePass 1:\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Min = 10 → placed at index 0\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Max = 100 → placed at index 6\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Current Sorted Array: [10, None, None, None, None, None, 100]\u003c/p\u003e\n\u003cp\u003e--------------------------------------------------\u003c/p\u003e\n\u003cp\u003ePass 2:\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Min = 20 → placed at index 1\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Max = 70 → placed at index 5\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Current Sorted Array: [10, 20, None, None, None, 70, 100]\u003c/p\u003e\n\u003cp\u003e--------------------------------------------------\u003c/p\u003e\n\u003cp\u003ePass 3:\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Min = 30 → placed at index 2\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Max = 60 → placed at index 4\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Current Sorted Array: [10, 20, 30, None, 60, 70, 100]\u003c/p\u003e\n\u003cp\u003e--------------------------------------------------\u003c/p\u003e\n\u003cp\u003ePass 4:\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Extracted Min = 50 → placed at index 3\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; Current Sorted Array: [10, 20, 30, 50, 60, 70, 100]\u003c/p\u003e\n\u003cp\u003e--------------------------------------------------\u003c/p\u003e\n\u003cp\u003eFinal Sorted Array: [10, 20, 30, 50, 60, 70, 100]\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e2.6 Complexity Analysis\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e2.6.1 Time Complexity\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThe proposed Double-Ended Heap-Based Min-Max Sorting Algorithm operates in two major phases. The first phase involves heap construction, where both a min-heap and a max-heap are built from the input array of size n. Since building each heap requires linear time, the total cost of this step is T\u003csub\u003ebuild\u003c/sub\u003e (n) = O(n) + O(n) = O(n).\u003c/p\u003e\n\u003cp\u003eThe second phase consists of iterative extraction, where in each pass, the minimum and maximum elements are removed from the heaps and placed into their respective positions in the sorted array. Extracting an element from a heap requires O(log n) time, and since both a minimum and a maximum are extracted in each iteration, the total cost per pass is 2\u0026nbsp;⋅\u0026nbsp;O(log n).\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eWith\u0026nbsp;⌈n/2⌉\u0026nbsp;iterations needed to process the entire array, the overall extraction cost becomes T\u003csub\u003eextract\u0026nbsp;\u003c/sub\u003e(n) =\u0026nbsp;⌈n/2⌉ ⋅\u0026nbsp;2\u0026nbsp;⋅\u0026nbsp;O(log n) = O(n log n). Therefore, the total time complexity of the algorithm is the sum of heap construction and extraction, expressed as\u003c/p\u003e\n\u003cp\u003eT(n) = \u0026nbsp;T\u003csub\u003ebuild\u003c/sub\u003e (n) + T\u003csub\u003eextract\u0026nbsp;\u003c/sub\u003e(n) = O(n) + O(n log n) = O(n log n).\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e2.6.2 Space Complexity\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThe space requirement of the proposed algorithm is primarily determined by the additional data structures used during execution. In the current implementation, three extra arrays are allocated: the min-heap, which requires O(n) space to store all elements; the max-heap, which also requires O(n) space since it holds the negated copy of the array; and the sorted_arr, which is an auxiliary array of size n used to store the final output. Therefore, the overall auxiliary space requirement can be expressed as S(n) = O(n) + O(n) + O(n) = O(n).\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eAlthough the algorithm fills the sorted array step by step during the extraction phase, the use of additional heaps means that it is not an in-place algorithm. Consequently, the space complexity of the current version remains O(n) rather than O(1).\u003c/p\u003e"},{"header":"3. Experimental Results","content":"\u003cp\u003eThe main findings of the proposed Double-Ended Heap-Based Min-Max Sorting Algorithm are summarized in Table\u0026nbsp;\u003cspan refid=\"Tab1\" class=\"InternalRef\"\u003e1\u003c/span\u003e \u0026ndash; Table\u0026nbsp;\u003cspan refid=\"Tab3\" class=\"InternalRef\"\u003e3\u003c/span\u003e. The results are based on arrays of different sizes generated randomly.\u003c/p\u003e\u003cp\u003e\u003cdiv class=\"gridtable\"\u003e\u003ctable float=\"Yes\" id=\"Tab1\" border=\"1\"\u003e\u003ccaption language=\"En\"\u003e\u003cdiv class=\"CaptionNumber\"\u003eTable 1\u003c/div\u003e\u003cdiv class=\"CaptionContent\"\u003e\u003cp\u003eExecution Time for Different Array Sizes\u003c/p\u003e\u003c/div\u003e\u003c/caption\u003e\u003ccolgroup cols=\"3\"\u003e\u003cdiv align=\"left\" class=\"colspec\" colname=\"c1\" colnum=\"1\"\u003e\u003c/div\u003e\u003cdiv align=\"char\" char=\".\" class=\"colspec\" colname=\"c2\" colnum=\"2\"\u003e\u003c/div\u003e\u003cdiv align=\"left\" class=\"colspec\" colname=\"c3\" colnum=\"3\"\u003e\u003c/div\u003e\u003cthead\u003e\u003ctr\u003e\u003cth align=\"left\" colname=\"c1\"\u003e\u003cp\u003eArray Size (n)\u003c/p\u003e\u003c/th\u003e\u003cth align=\"left\" colname=\"c2\"\u003e\u003cp\u003eTime Taken (ms)\u003c/p\u003e\u003c/th\u003e\u003cth align=\"left\" colname=\"c3\"\u003e\u003cp\u003eComplexity\u003c/p\u003e\u003c/th\u003e\u003c/tr\u003e\u003c/thead\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e1,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e2.3\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"left\" colname=\"c3\"\u003e\u003cp\u003eO(n log n)\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e2,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e5.1\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"left\" colname=\"c3\"\u003e\u003cp\u003eO(n log n)\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e5,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e13.0\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"left\" colname=\"c3\"\u003e\u003cp\u003eO(n log n)\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e10,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e28.7\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"left\" colname=\"c3\"\u003e\u003cp\u003eO(n log n)\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e20,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e62.4\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"left\" colname=\"c3\"\u003e\u003cp\u003eO(n log n)\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/colgroup\u003e\u003c/table\u003e\u003c/div\u003e\u003c/p\u003e\u003cp\u003eTable\u0026nbsp;\u003cspan refid=\"Tab1\" class=\"InternalRef\"\u003e1\u003c/span\u003e shows the execution time measured on a standard CPU for different array sizes. The time grows approximately proportionally to n log n, as expected.\u003c/p\u003e\u003cp\u003e\u003cdiv class=\"gridtable\"\u003e\u003ctable float=\"Yes\" id=\"Tab2\" border=\"1\"\u003e\u003ccaption language=\"En\"\u003e\u003cdiv class=\"CaptionNumber\"\u003eTable 2\u003c/div\u003e\u003cdiv class=\"CaptionContent\"\u003e\u003cp\u003eMemory (Auxiliary Space) Usage\u003c/p\u003e\u003c/div\u003e\u003c/caption\u003e\u003ccolgroup cols=\"2\"\u003e\u003cdiv align=\"left\" class=\"colspec\" colname=\"c1\" colnum=\"1\"\u003e\u003c/div\u003e\u003cdiv align=\"char\" char=\".\" class=\"colspec\" colname=\"c2\" colnum=\"2\"\u003e\u003c/div\u003e\u003cthead\u003e\u003ctr\u003e\u003cth align=\"left\" colname=\"c1\"\u003e\u003cp\u003eArray Size (n)\u003c/p\u003e\u003c/th\u003e\u003cth align=\"left\" colname=\"c2\"\u003e\u003cp\u003eExtra Space Used (KB)\u003c/p\u003e\u003c/th\u003e\u003c/tr\u003e\u003c/thead\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e1,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e8\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e2,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e16\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e5,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e40\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e10,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e80\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003e20,000\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e160\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/colgroup\u003e\u003c/table\u003e\u003c/div\u003e\u003c/p\u003e\u003cp\u003eTable\u0026nbsp;\u003cspan refid=\"Tab2\" class=\"InternalRef\"\u003e2\u003c/span\u003e shows that the algorithm requires O(n) extra space due to the separate min-heap and max-heap structures.\u003c/p\u003e\u003cp\u003e\u003cdiv class=\"gridtable\"\u003e\u003ctable float=\"Yes\" id=\"Tab3\" border=\"1\"\u003e\u003ccaption language=\"En\"\u003e\u003cdiv class=\"CaptionNumber\"\u003eTable 3\u003c/div\u003e\u003cdiv class=\"CaptionContent\"\u003e\u003cp\u003eHeap Operation Times (Average per Operation)\u003c/p\u003e\u003c/div\u003e\u003c/caption\u003e\u003ccolgroup cols=\"3\"\u003e\u003cdiv align=\"left\" class=\"colspec\" colname=\"c1\" colnum=\"1\"\u003e\u003c/div\u003e\u003cdiv align=\"char\" char=\".\" class=\"colspec\" colname=\"c2\" colnum=\"2\"\u003e\u003c/div\u003e\u003cdiv align=\"char\" char=\".\" class=\"colspec\" colname=\"c3\" colnum=\"3\"\u003e\u003c/div\u003e\u003cthead\u003e\u003ctr\u003e\u003cth align=\"left\" colname=\"c1\"\u003e\u003cp\u003eOperation\u003c/p\u003e\u003c/th\u003e\u003cth align=\"left\" colname=\"c2\"\u003e\u003cp\u003eMin-Heap (ms)\u003c/p\u003e\u003c/th\u003e\u003cth align=\"left\" colname=\"c3\"\u003e\u003cp\u003eMax-Heap (ms)\u003c/p\u003e\u003c/th\u003e\u003c/tr\u003e\u003c/thead\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003eBuild Heap\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e1.1\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c3\"\u003e\u003cp\u003e1.2\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003eExtract Element\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e0.05\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c3\"\u003e\u003cp\u003e0.06\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align=\"left\" colname=\"c1\"\u003e\u003cp\u003eInsert Element\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c2\"\u003e\u003cp\u003e0.04\u003c/p\u003e\u003c/td\u003e\u003ctd align=\"char\" char=\".\" colname=\"c3\"\u003e\u003cp\u003e0.05\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/colgroup\u003e\u003c/table\u003e\u003c/div\u003e\u003c/p\u003e\u003cp\u003eTable\u0026nbsp;\u003cspan refid=\"Tab3\" class=\"InternalRef\"\u003e3\u003c/span\u003e shows the average time for key heap operations. Build heap takes the most time, while insert and extract operations are very fast.\u003c/p\u003e"},{"header":"4. Discussion","content":"\u003cp\u003eThe results of the proposed Double-Ended Heap-Based Min-Max Sorting Algorithm demonstrate that the method achieves an overall time complexity of O(n log n), which is consistent with the efficiency of classical comparison-based algorithms such as Heap Sort and Merge Sort. However, unlike traditional approaches, the algorithm explicitly places both minimum and maximum values at each iteration, providing pedagogical clarity while still maintaining computational efficiency. The performance comparison also highlights that, while the algorithm requires O(n) additional space due to the use of auxiliary heaps, it still outperforms quadratic-time algorithms such as Selection Sort or Bubble Sort for larger input sizes.\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003cp\u003eFigure\u0026nbsp;\u003cspan refid=\"Fig1\" class=\"InternalRef\"\u003e1\u003c/span\u003e. shows the execution time of the proposed Double-Ended Heap-Based Min-Max Sorting Algorithm (O(n log n)) compared with a standard O(n\u0026sup2;) algorithm (e.g., Min-Max Sorting Algorithm) for arrays of different sizes. The graph illustrates that as the array size increases, the O(n log n) algorithm scales more efficiently, while the O(n\u0026sup2;) algorithm\u0026rsquo;s execution time grows significantly faster.\u003c/p\u003e\u003cp\u003eWhen compared with previous studies on heap-based and selection-based sorting methods, this algorithm shows distinctive advantages in terms of its dual-end placement strategy. Prior research has focused primarily on either min-heap or max-heap extraction for sorting, but few studies have explicitly combined both operations in a single unified framework. The findings suggest that this dual extraction not only improves conceptual understanding but may also offer opportunities for parallelization, which is less emphasized in conventional algorithms.\u003c/p\u003e\u003cp\u003eOne of the distinctive advantages of the proposed algorithm is the reduced number of passes, since both ends of the array are filled simultaneously through dual heap extractions. This contributes not only to efficiency but also to pedagogical clarity in algorithm visualization.\u003c/p\u003e\u003cp\u003eThe observed efficiency can be attributed to the logarithmic extraction cost of heaps and the simultaneous processing of two elements per iteration. Nevertheless, the additional space requirement represents a trade-off compared to strictly in-place algorithms such as Quick Sort or Heap Sort. Another possible limitation is that the algorithm\u0026rsquo;s performance advantage may not be as pronounced for small datasets, where the overhead of maintaining two heaps could outweigh the benefits of dual extraction.\u003c/p\u003e\u003cp\u003eFinally, while the proposed method demonstrates both theoretical and pedagogical value, its current design may be further improved by exploring in-place modifications to reduce memory consumption, as well as testing parallel heap extractions on modern multi-core systems. These avenues represent promising directions for future research.\u003c/p\u003e"},{"header":"5. Conclusion","content":"\u003cp\u003eThis study introduced the Double-Ended Heap-Based Min-Max Sorting Algorithm, a novel approach that combines the use of min-heaps and max-heaps to simultaneously extract and place the smallest and largest elements during each iteration. The algorithm achieves an overall time complexity of O(n log n), making it efficient compared to quadratic-time methods, while its dual-end placement strategy enhances pedagogical clarity and visualization of the sorting process. The algorithm reduces the number of passes by combining dual-end extraction, making it suitable for both practical applications and teaching environments. Although the current implementation requires O(n) auxiliary space, it demonstrates strong potential for practical applications where dual-ended ordering is desirable. Future research should focus on optimizing the algorithm to operate in-place with reduced memory overhead and exploring parallel heap extraction techniques to further enhance its efficiency in large-scale computational settings.\u003c/p\u003e"},{"header":"Declarations","content":"\u003ch2\u003eAuthor Contribution\u003c/h2\u003e\u003cp\u003eMd. Mafiul Hasan Matin was solely responsible for the conception, design, implementation, analysis, and writing of this work.\u003c/p\u003e\u003cp\u003e\u003cstrong\u003eFunding\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThis research received no external funding.\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\n\u003cli\u003eMin, W. (2010, July). Analysis on bubble sort algorithm optimization. In \u003cem\u003e2010 International forum on information technology and applications\u003c/em\u003e (Vol. 1, pp. 208-211). IEEE.\u003c/li\u003e\n\u003cli\u003eLobo, J., \u0026amp; Kuwelkar, S. (2020, July). Performance analysis of merge sort algorithms. In \u003cem\u003e2020 International Conference on Electronics and Sustainable Communication Systems (ICESC)\u003c/em\u003e (pp. 110-115). IEEE.\u003c/li\u003e\n\u003cli\u003eHoare, C. A. (1962). Quicksort. \u003cem\u003eThe computer journal\u003c/em\u003e, \u003cem\u003e5\u003c/em\u003e(1), 10-16.\u003c/li\u003e\n\u003cli\u003eSchaffer, R., \u0026amp; Sedgewick, R. (1993). The analysis of heapsort. \u003cem\u003eJournal of Algorithms\u003c/em\u003e, \u003cem\u003e15\u003c/em\u003e(1), 76-100.\u003c/li\u003e\n\u003cli\u003ePathak, N., \u0026amp; Tiwari, S. (2017). Improved Double Selection Sort using Algorithm. \u003cem\u003eSAMRIDDHI: A Journal of Physical Sciences, Engineering and Technology\u003c/em\u003e, \u003cem\u003e9\u003c/em\u003e(02), 85-88.\u003c/li\u003e\n\u003cli\u003eMuthusundari, S., Beevi, L. S., Shankar, G., Archana, U., \u0026amp; Nirmala, G. (2024). A Mathematical based Divide and Conquer Approach to a New Sorting Algorithm with Min Max Index Value. \u003cem\u003eJournal of Internet Services and Information Security\u003c/em\u003e, \u003cem\u003e13\u003c/em\u003e(1), 85-94.\u003c/li\u003e\n\u003cli\u003eMantere, T. (2006). A min-max genetic algorithm with alternating multiple sorting for solving constrained problems. In \u003cem\u003eProceedings of the Ninth Scandinavian Conference on Artificial Intelligence (SCAI 2006)\u003c/em\u003e (pp. 61-67). Finnish Artificial Intelligence Society.\u003c/li\u003e\n\u003cli\u003eGoyani, M., Chharchhodawala, M., \u0026amp; Mendapara, B. (2013). Min-max selection sort algorithm\u0026ndash;improved version of selection sort. \u003cem\u003eInt. J. Adv. Res. Comput. Sci. Softw. Eng\u003c/em\u003e, \u003cem\u003e6\u003c/em\u003e.\u003c/li\u003e\n\u003cli\u003eAgarwal, A., Pardesi, V., Agarwal, N., Tech, M., Tech, C. N. M., DTU, D. B., \u0026amp; BITS, S. (2013). A new approach to sorting: min-max sorting algorithm. \u003cem\u003eSORT\u003c/em\u003e, \u003cem\u003e2\u003c/em\u003e(2), n2.\u003c/li\u003e\n\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Sorting Algorithm, Min-Max Heap, Dual-Ended Sorting, Computational Efficiency, Algorithm Optimization","lastPublishedDoi":"10.21203/rs.3.rs-7665270/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7665270/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eSorting 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 \u0026lceil;n/2\u0026rceil; 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\u0026rsquo;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.\u003c/p\u003e","manuscriptTitle":"Double-Ended Heap-Based Min-Max Sorting Algorithm: A Novel Approach for Efficient Dual-End Placement Sorting","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-09-23 06:26:36","doi":"10.21203/rs.3.rs-7665270/v1","editorialEvents":[{"type":"communityComments","content":2}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"49ce9454-d771-4ffd-acb2-4994b8deedce","owner":[],"postedDate":"September 23rd, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-10-13T01:53:39+00:00","versionOfRecord":[],"versionCreatedAt":"2025-09-23 06:26:36","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7665270","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7665270","identity":"rs-7665270","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}