HIPM Sort: A Heap–Insertion–Pivot–Merge Hybrid Sorting Algorithm and Its Empirical Comparison With Classical Sorting Algorithms

Abstract

Sorting is one of the most frequently used operations in computing, yet no classical algorithm is best fitted for every data size and distribution. This paper proposes HIPM Sort (Heap–Insertion–Pivot–Merge Sort), a hybrid comparison sort that builds a min-heap to impose a partial order, partitions the second half of the array around the element at position 3n/4, sorts each half with insertion sort, and merges the halves. We review bubble, selection, insertion, Shell, merge, heap, quick and Tim sort with their advantages and disadvantages, derive the complexity of HIPM Sort (O(n) best, O(n²) average and worst, O(n) space), and compare it with all eight algorithms on 100 random arrays of 100 integers. HIPM Sort removes about 74% of the element shifts of insertion sort, matches quick sort at n = 100 (median 3.0 µs versus 3.1 µs), and is 2.0× faster than insertion sort at n = 1000. Its quadratic growth, however, makes it about 3× slower than quick sort at n = 5000, so it is best suited to small and medium arrays. Its recursive version may yield a better result instead of insertion sort while combined with merge sort like in Shell sort and Tim-sort algorithms.