20 Multicriterion Analysis
of Fusion Sort
A Hybrid Approach to
Sorting Algorithms
Sathvik V Koushik, Shamanth Showri N R,
Shreya C R, Urjitha P, and Divya C D
20.1 INTRODUCTION
Efficient sorting algorithms play a pivotal role in diverse data processing tasks,
directly influencing overall computational efficiency (Satish et al., 2009). This
research addresses the challenge of sorting data sets with intermediate sizes by
designing a novel algorithm.
Previous researchers have extensively explored various sorting algorithms and
their performance under different scenarios. Hoare (1962) conducted an empirical
study comparing Quick Sort, Merge Sort, and Insertion Sort on large data sets, shed-
ding light on each algorithm’s relative strengths and weaknesses. Bentley (1980) AuQ44
introduced a divide and conquer approach optimized for large data sets, but its effi-
ciency diminished with smaller arrays.
Estivill-Castro et al. (1992) explored adaptive sorting algorithms, discussing
theoretical contributions in complexity and disorder measures, practical insights
into adaptivity, and faster alternatives for nearly sorted sequences. Al-Kharabsheh
et al. (2013) investigated sorting algorithms, comparing Grouping Comparison
Sort with conventional methods for improved performance. While established
sorting techniques like Quick Sort (Hoare, 1962; Steier et al., 1989) and Merge AuQ45
Sort (Cole, 1988) are widely used and respected for their efficacy, they may not AuQ46
always be the most efficient choices for data sets falling within this specific size
range.
Sedgewick (1978) presented the practical implementation of Quick Sort and its
variants on real computers to optimize performance while minimizing extra storage
usage and summarized the analytic performance results. Rösler (1991) examined the
number of comparisons performed by Quick Sort and established the convergence of
the random variable (Xn—E(Xn))/n to Y, and Y exhibited exponential tails, indicat-
ing efficient sorting performance. TimSort’s adoption as the standard sorting algo-
rithm in Java and Python challenges the perception of merge algorithms’ inefficiency.
Other researchers developed a new framework and a simpler competitive algorithm
and confirmed O(n log n) running time for TimSort (Auger et al., 2015). One group
DOI: 10.1201/9781032635170-20 263
264 Multi-Criteria Decision-Making with Machine Learning
compared five merge sorting algorithms for large data sets on FPGA, determining
the best algorithm based on resource utilization, delay, and area comparisons (Lobo
et al., 2020). Another found that a hybrid sort algorithm outperformed bitonic merge
sort and bitonic odd–even sort with increased input bit width, achieving three times
faster processing time through pipelining and parallel processing (Harshini et al.,
2019).
De Micco et al. (2019) introduced a hybrid data ordering algorithm, combining
serial and parallel instructions for sorting, performing complexity analysis, and com-
paring it with other sorting algorithms are presented. Lakshmivarahan et al. (1984)
studied parallel sorting algorithms, vital for commercial applications, in relation to
parallel computer architecture, covering fixed interconnection networks and global
memory models. Special-purpose network-sorting and SIMD machine algorithms
are included.
Blelloch et al. (1991) compared three parallel sorting algorithms on the CM-2
Supercomputer and found that sample sort outperformed the others on large data
sets, while radix sort was stable, and bitonic sort was space efficient. Estivill-
Castro et al. (1992) explored adaptive sorting algorithms’ contributions in theory
and practice, discussing complexity descriptions and introducing faster algorithms
for nearly sorted sequences, and a different group found that Selection Sort out-
performed Quick Sort for integer and string arrays, with an upper bound running
time of O(n) (Aliyu et al., 2013). Khandelwal (2021) discussed the significance of AuQ47
efficient sorting algorithms in various fields, presenting an analysis of parallel and
sequential algorithms on different GPU and CPU architectures, exploiting task
parallelism.
In this work, we present Fusion Sort, a novel hybrid sorting algorithm tailored
to effectively manage data sets of intermediate sizes. By harnessing the advantages
of both Insertion Sort and divide and conquer, Fusion Sort dynamically adapts its
sorting approach based on a carefully selected threshold. For smaller subarrays, it
efficiently employs Insertion Sort, capitalizing on its superior performance for such
data; for larger subarrays, it seamlessly switches to divide and conquer, leveraging its
efficiency in handling bigger data sets.
Extensive experimental evaluations underscore the superiority of Fusion Sort
over Quick Sort and Merge Sort for intermediate-sized data sets. Its adaptive nature
empowers Fusion Sort to outperform traditional sorting algorithms in this specific
context, making it an appealing choice for real-world applications that frequently
encounter data sets of moderate sizes. This study provides an in-depth analysis of
Fusion Sort’s algorithmic steps, complexity, and experimental results, substantiating
its standing as a practical and robust sorting solution for data sets within the inter-
mediate size range.
20.2 PROBLEM STATEMENT
Efficient sorting algorithms serve as the backbone of various data processing tasks,
significantly impacting the overall computational efficiency (Satish et al., 2009).
Sorting algorithms, such as Quick Sort and Merge Sort, have been extensively stud-
ied and are well established for large data sets. However, there exists a unique chal-
lenge in the realm of data sorting: data sets of intermediate sizes. While large data
sets have their dedicated sorting strategies, and small data sets can be efficiently
Multicriterion Analysis of Fusion Sort 265
managed with algorithms like Insertion Sort, the sorting of intermediate-sized data
sets has received relatively less attention. We sought to fill this gap in the research
by presenting Fusion Sort and conducting a comprehensive comparative analysis to
demonstrate its efficacy and superiority in handling data sets within the intermediate
size range.
20.3 THE PROPOSED WORK
20.3.1 Methodology
[Link] Experimental Setup
To evaluate the performance of Fusion Sort, we set up a series of experiments using
data sets of different sizes and characteristics. We describe the sets we used, includ-
ing synthetic data sets with random elements and real-world data sets representing
diverse data types.
[Link] Threshold Selection
The threshold plays a crucial role in the performance of Fusion Sort. We experi-
mented with different thresholds to identify the best one for intermediate input sizes.
After thorough analysis, we found that a threshold of 34 yielded the optimal results
for medium-sized data sets.
[Link] Comparative Algorithms
To assess Fusion Sort’s efficiency, we select two well-established sorting algorithms,
Quick Sort and Merge Sort, as benchmarks for comparison. We briefly outline the
working principles of each algorithm and their respective complexities.
[Link] Performance Metrics
We define the performance metrics used to evaluate the sorting algorithms’ effi-
ciency. These metrics include average-case time complexity and the number of com-
parisons performed during the sorting process.
[Link] Experimental Procedure
We conduct a series of experiments with varying input sizes to measure the perfor-
mance of Fusion Sort, Quick Sort, and Merge Sort. Each experiment is repeated mul-
tiple times to ensure statistical significance. We describe the steps taken to eliminate
biases and ensure fair comparisons between the algorithms.
[Link] Data Analysis
After conducting the experiments, we compare the accuracy of Fusion Sort with that of
Quick Sort and Merge Sort. We present the experimental data in graphical form, high-
lighting the performance differences among the algorithms for different data set sizes.
20.3.2 Algorithms
Fusion Sort is a hybrid sorting algorithm that combines the strengths of Insertion
Sort and divide and conquer to achieve accurate and effective sorting performance.
266 Multi-Criteria Decision-Making with Machine Learning
This algorithm optimizes the sorting process by employing Insertion Sort on smaller
subarrays and divide and conquer on larger subarrays. The algorithm uses a user-
specified threshold value to determine when to switch between the two strategies.
[Link] Algorithm: Fusion Sort
Input: An unsorted array of comparable elements.
Threshold: An integer representing the threshold value that determines when
to use Insertion Sort on smaller subarrays.
Output: A sorted array in ascending order.
function fusion _ sort(arr, threshold)
if the length of arr ≤ threshold then
return insertion_sort(arr[:]) # Create a new list
to sort and return
end if
pivot = choose _ pivot(arr)
smaller _ subarray, larger _ subarray = partition(arr,
pivot)
smaller _ subarray = fusion _ sort(smaller _ subar-
ray, threshold)
larger _ subarray = fusion _ sort(larger _ subarray,
threshold)
merged _ arr = merge(smaller _ subarray, [pivot],
larger _ subarray)
return merged _ arr
end function
[Link] Algorithm: Choose Pivot
Input: An array ‘arr’ for which the pivot needs to be chosen.
Output: The pivot element (e.g., the median of the first, middle, and last ele-
ments in the array).
function choose _ pivot(arr)
# Choose the pivot element (e.g., median of the
first, middle, and last elements)
return sorted([arr[0], arr[length of arr // 2], arr[-
1]])[1]
end function
[Link] Algorithm: Partition
Input: An array ‘arr’ and a pivot element ‘pivot’ for which the array needs to
be partitioned.
Output: Two subarrays: ‘smaller_subarray’ containing elements less than the
pivot, and ‘larger_subarray’ containing elements greater than the pivot.
function partition(arr, pivot)
smaller _ subarray = [ ]
larger _ subarray = []
Multicriterion Analysis of Fusion Sort 267
for x in arr do
if x < pivot then
append x to smaller _ subarray
else if x > pivot then
append x to larger _ subarray
end if
end for
return smaller _ subarray, larger _ subarray
end function
[Link] Algorithm: Insertion Sort
Input: An unsorted array ‘arr’.
Output: The sorted array ‘arr’ in ascending order.
function insertion _ sort(arr)
for i from 1 to length of arr − 1 do
key = arr[i]
j = i − 1
while j ≥ 0 and arr[j] > key do
arr[j + 1] = arr[j]
j = j − 1
end while
arr[j + 1] = key
end for
return arr
end function
[Link] Algorithm: Merge Arrays
Input: Three sorted arrays—arr1, arr2, and arr3
Output: Merged sorted array containing all elements from arr1, arr2, and arr3
function merge(arr1, arr2, arr3)
merged _ arr = []
i = j = k = 0
while i < length of arr1 and j < length of arr2 and
k < length of arr3 do
if arr1[i] ≤ arr2[j] and arr1[i] ≤ arr3[k] then
append arr1[i] to merged _ arr
i = i + 1
else if arr2[j] ≤ arr1[i] and arr2[j] ≤ arr3[k] then
append arr2[j] to merged _ arr
j = j + 1
else
append arr3[k] to merged _ arr
k = k + 1
end if
end while
while i < length of arr1 do
268 Multi-Criteria Decision-Making with Machine Learning
append arr1[i] to merged _ arr
i = i + 1
end while
while j < length of arr2 do
append arr2[j] to merged _ arr
j = j + 1
end while
while k < length of arr3 do
append arr3[k] to merged _ arr
k = k + 1
end while
return merged _ arr
end function
20.4 RESULTS AND DISCUSSION
We present the experimental results obtained from evaluating the Fusion Sort algo-
rithm and compare it with Quick Sort and Merge Sort. We conducted a compre-
hensive set of experiments using data sets of different sizes and characteristics and
repeated the experiments multiple times to ensure statistical significance, and the
average results are reported here.
20.5 PERFORMANCE ANALYSIS
20.5.1 Execution Time
The average time taken by each algorithm to sort the small, medium, and large data
sets (Figures 20.1 to 20.3).
FIGURE 20.1 Execution time for small input sizes.
Multicriterion Analysis of Fusion Sort 269
FIGURE 20.2 Execution time for medium input sizes.
FIGURE 20.3 Execution time for large input sizes.
20.5.2 Number of Comparisons
The total number of element comparisons made during the sorting process for the
small, medium, and large data sets (Figures 20.4 to 20.6); fewer comparisons indi-
cate higher accuracy.
270 Multi-Criteria Decision-Making with Machine Learning
FIGURE 20.4 Number of comparisons for small input sizes.
FIGURE 20.5 Number of comparisons for medium input sizes.
20.5.3 Time Complexity
To derive the time complexity of Fusion Sort, we need to analyze the number of
operations performed at each step of the algorithm. Let’s break down the time com-
plexity analysis step by step:
Multicriterion Analysis of Fusion Sort 271
FIGURE 20.6 Number of comparisons for large input sizes.
Choosing the Pivot:
• The ‘choose_pivot’ function selects the pivot element in O(1) time as it
only involves basic array indexing and comparisons.
Partitioning the Array:
• The ‘partition’ function divides the input array into two subarrays based
on the pivot element in linear time, O(n), where n is the size of the input
array. It iterates through the array once and assigns each element to one
of the two subarrays.
Recursive Calls:
• Fusion Sort recursively calls itself on ‘smaller_subarray’ and ‘larger_
subarray’. The size of these subarrays is proportional to the size of the
original array.
Merging the Subarrays:
• ‘Merge’ combines the sorted subarrays and the pivot element into a sin-
gle sorted array in linear time, O(n), where n is the total number of ele-
ments in the input array.
Let T(n) represent the time complexity of Fusion Sort for an input array of size n. The
time complexity can be expressed as a recurrence relation:
T(n) = 2 x T(n/2) + O(n) (20.1)
The recurrence relation is derived from the two recursive calls in Step 1, and the time
complexity for merging the subarrays in Step 5.
272 Multi-Criteria Decision-Making with Machine Learning
Using the Master Theorem, we can solve the recurrence relation.
For the given recurrence relationship:
a = 2 (number of recursive calls),
b = 2 (size of the subproblems),
f(n) = O(n) (time complexity for merging the subarrays).
Since f(n) = O(n) falls under Case 1 of the Master Theorem (where f(n) = O(nc) and
c < logb(a)), the overall time complexity of Fusion Sort can be determined as follows:
T(n) = Θ(nlog n) (20.2)
Thus, the time complexity of Fusion Sort is Θ(nlog n), which makes it more efficient
than traditional sorting algorithms like Quick Sort and Merge Sort for data sets of
intermediate sizes. For small subarrays (size ≤ threshold), the time complexity is
O(k2), where k is the size of the subarray, due to the use of Insertion Sort. This adap-
tive nature of Fusion Sort contributes to its superior performance for data sets of
varying sizes and characteristics.
20.6 CONCLUSION
Fusion Sort emerges as a highly efficient sorting algorithm tailored for data sets
with intermediate sizes. By judiciously combining Insertion Sort with divide and
conquer, Fusion Sort performed well in scenarios where sorting intermediate-sized
data sets is a common requirement. Its dynamic, seamless handling of varying input
sizes makes Fusion Sort a valuable and versatile addition to the domain of sorting
algorithms, offering a better solution for the real-world sorting of data sets of moder-
ate dimensions. The algorithm’s ability to adapt to different data set characteristics
and deliver superior performance sets it apart as a valuable tool for enhancing data
processing accuracy and efficiency across diverse computational tasks.
REFERENCES
Aliyu, Ahmed M., and P. B. Zirra. “A comparative analysis of sorting algorithms on inte-
ger and character arrays.” The International Jornal of Engineering and Science (2013):
25–30. ISSN(e): 2319–1813, [Link] repid=rep1&type=
pdf&doi=b8b872f7cb7b08cd61088cbf55aa2e42221b23a7
Al-Kharabsheh, Khalid Suleiman, et al. “Review on sorting algorithms a comparative study.”
International Journal of Computer Science and Security (IJCSS) 7.3 (2013): 120–126,
[Link]
Auger, Nicolas, Cyril Nicaud, and Carine Pivoteau. “Merge strategies: From merge sort to
Timsort.” (2015), [Link]
Bentley, Jon Louis. “Multidimensional divide-and-conquer.” Communications of the ACM
23.4 (1980): 214–229, [Link]
Blelloch, Guy E., et al. “A comparison of sorting algorithms for the connection machine
CM-2.” Proceedings of the Third Annual ACM Symposium on Parallel algorithms and
Architectures. (1991), [Link]
Cole, Richard. “Parallel merge sort.” SIAM Journal on Computing 17.4 (1988): 770–785,
[Link]
Multicriterion Analysis of Fusion Sort 273
De Micco, Luciana, Mariano L. Acosta, and Maximiliano Antonelli. “Hybrid sorting algo-
rithm implemented by high level synthesis.” IEEE Latin America Transactions 18.02
(2019): 430–437, [Link]
Estivill-Castro, Vladmir, and Derick Wood. “A survey of adaptive sorting algorithms.”
ACM Computing Surveys (CSUR) 24.4 (1992): 441–476, [Link]
146381
Harshini, V. S., and KK Senthil Kumar. “Design of hybrid sorting unit.” 2019 International
Conference on Smart Structures and Systems (ICSSS). IEEE (2019), [Link]
org/10.1109/ICSSS.2019.8882866
Hoare, Charles A. R. “Quicksort.” The Computer Journal 5.1 (1962): 10–16, [Link]
org/10.1093/comjnl/5.1.10
Khandelwal, Vikram. “Analysis and review of sorting algorithms.” International Journal of
Algorithms Design and Analysis 7.2 (2021): 1–5, [Link]
[Link]?journal=JADA&page=article&op=view&path[]=740
Lakshmivarahan, S., Sudarshan K. Dhall, and Leslie L. Miller. “Parallel sorting algo-
rithms.” Advances in Computers 23. Elsevier (1984): 295–354, [Link]
S0065-2458(08)60467-2
Lobo, Joella, and Sonia Kuwelkar. “Performance analysis of merge sort algorithms.” 2020
International Conference on Electronics and Sustainable Communication Systems
(ICESC). IEEE (2020), [Link]
Rösler, Uwe. “A limit theorem for ‘Quicksort’.” RAIRO-Theoretical Informatics and
Applications 25.1 (1991): 85–100, [Link]
25_1_85_0
Satish, Nadathur, Mark Harris, and Michael Garland. “Designing efficient sorting algorithms
for manycore GPUs.” 2009 IEEE International Symposium on Parallel & Distributed
Processing. IEEE (2009), [Link]
Sedgewick, Robert. “Implementing quicksort programs.” Communications of the ACM 21.10
(1978): 847–857, [Link]
Steier, D. M., et al. “Quicksort.” Algorithm Synthesis: A Comparative Study (1989): 24–38,
[Link]