Performing hybrid sorts using C++

By MRINAL SINHA

Sorting the given elements using C++ , which has better time complexity than regular Merge and Quick Sorts .

HYBRID SORTS :

A hybrid algorithm is a combination of two or more algorithms that solve the same problem. Algorithms are selected depending on the data and switching between them over the course of the algorithm. This is done to combine desired features of each so that the overall algorithm is better than the individual components.

Hybrid algorithms exploit the good properties of different methods by applying them to problems they can efficiently solve. For example, the search is efficient when the problem has many solutions, while inference is efficient in proving the unsatisfiability of overconstrained problems.

Examples of hybrid sorts are :

1. Tim Sort
2. Quick_Insert Sort

TIM SORT :

It is a highly optimized hybrid sorting algorithm. Tim Sort combines merge sort, insertion sort, together with additional logic (including binary search) in the merging logic.
The first small pieces are sorted using Insertion Sort, then merges the pieces using a merge of merge sort, to get the desired sorted array.

IMPORTANT :

We should break the array into pieces of size 32-64, as insertion sort works well on a small number of elements.
After sorting individual pieces, we merge them one by one.

TIME COMPLEXITY: The algorithm works in O(n log n) time.

 

QUICK_INSERT SORT :

The Quicksort is one of the fastest sorting algorithms for sorting large lists of data and the Insertion sort is a fast sorting algorithm for sorting very small lists of data.
Thus these two sorts can be combined to come up with a very simple and effective method for sorting large lists.

IMPORTANT :

We should break the array into pieces of size 32-64, as insertion sort works well on a small number of elements.
QuickSort is performed and when the size of pieces becomes in the range we perform Insertion sort.

TIME COMPLEXITY: The algorithm works in O(n log n) time.

REQUIREMENTS: Familiar with sorting algorithms and little knowledge in recursion and backtracking.