Optimizing Merge Sort: My Hybrid Approach and Performance Analysis

Hey, it’s me again. For my CSC 551 (Algorithm Design) assignment, I had to study the merge operation in merge sort the( O(n) part ), review a few implementations, and then create my own version. I ended up studying three different sorting algorithms, picked ideas from each, and built a hybrid merge sort. Here’s my write-up and the code.

Merge Sort uses a divide-and-conquer approach to sort arrays of elements. It works by dividing an unsorted array into subarrays until there is only one element, and then repeatedly merging these subarrays to produce new sorted subarrays until there is only one subarray remaining.

The merging process is the key part of the algorithm. It involves comparing elements from two sorted subarrays and placing them in the correct order in a new combined list.

The time complexity of Merge Sort is O(n log n) in all cases (best, average, and worst).

Variations of Merge Sort

1. Top-Down Merge Sort

This is the most common implementation of Merge Sort. It uses a recursive approach to divide the array into smaller subarrays and then merges them back together.

Read more top down merge sort code sample

2. Bottom-Up Merge Sort

This implementation uses an iterative approach to merge smaller subarrays into larger ones.

Read more Bottom-Up Merge Sort Code sample

3. Natural Merge Sort

This variation uses a technique called "natural merging" to reduce the number of comparisons required during the merging process.

Read more Natural Merge Sort code sample

Key differences:

• Top-Down is recursive, while Bottom-Up and Natural are iterative.

• Natural Merge Sort adapts to the input's existing order, potentially reducing the number of comparisons for partially sorted inputs.

• Bottom-Up Merge Sort has a fixed merging pattern, while Natural Merge Sort's merging pattern depends on the input.

4. My Merge Sort( Hybrid Merge sort) Implementation

My merge sort implementation uses an Hybrid Merge Sort(A combination of standard merge sort and bottom-up merge sort.

• Small array optimization: For arrays of size 32 or less, it uses insertion sort, which is faster for small arrays due to less overhead.

• Combines recursive and iterative approaches: It uses recursion for dividing the array (like standard merge sort) but optimizes the base case with insertion sort (similar to the philosophy of bottom-up merge sort).

• No in-place merging: Unlike other variations, it still uses additional space for merging, prioritizing speed over space efficiency. Hybrid Merge sort code

Analysis Report

summary analysis of the results:

All four variations of Merge Sort show a logarithmic increase in average time as the array size increases, which is consistent with the expected O(n log n) time complexity of Merge Sort algorithms.

Performance Ranking (from fastest to slowest for larger arrays [1,000,000 elements]):

1. Hybrid Merge Sort

2. Top-Down Merge Sort

3. Bottom-Up Merge Sort

4. Natural Merge Sort

Performance Ranking (from fastest to slowest for larger arrays [500,000 elements]):

1. Hybrid Merge Sort

2. Top-Down Merge Sort

3. Bottom-Up Merge Sort

4. Natural Merge Sort

Performance Ranking (from fastest to slowest for smaller arrays [100,000 elements]):

1. Hybrid Merge Sort

2. Top-Down Merge Sort

3. Bottom-Up Merge Sort

4. Natural Merge Sort

All four variations of Merge Sort show a logarithmic increase in average time as the array size increases, which is consistent with the expected O(n log n) time complexity of Merge Sort algorithms.
Hybrid Merge Sort consistently outperform others by 20-40%.

Link to the code test environment

note: this is solely for educational purpose.