Detailed description

Description:

I would like to contribute an implementation of the IntroSort (Introspective Sort) algorithm in C++.

IntroSort is a hybrid sorting algorithm that begins with QuickSort, switches to HeapSort when recursion depth exceeds a certain limit, and uses InsertionSort for small partitions. This makes it both fast in practice and worst-case optimal. In fact, it is the algorithm behind C++’s std::sort.

Proposed Changes:

Add a new file intro_sort.cpp under the sorting/ directory.
Implementation will include:
-QuickSort as the base algorithm
-Depth-limit detection to switch to HeapSort
-InsertionSort for small arrays
-Include time and space complexity in comments.
-Add sample test cases in main() for verification.

Benefits:

1)Adds a widely used, practical, and high-performance sorting algorithm.
2)Complements the existing collection of sorting algorithms.

Context

This change is important because IntroSort is one of the most widely used practical sorting algorithms, being the default in C++’s std::sort.

I would use it to:

• Compare its performance against other sorting algorithms already present in the repository.
• Demonstrate how hybrid algorithms can achieve both average-case speed (like QuickSort) and worst-case guarantees (like HeapSort).
• Provide learners with a clear example of how multiple sorting strategies can be combined effectively.

This can benefit other users by:

• Expanding the collection with a real-world industrial-strength sorting algorithm.
• Helping students and contributors understand why STL’s std::sort is so efficient.
• Serving as a reference for hybrid algorithm design.

Possible Implementation

The implementation of IntroSort in C++ can be structured as follows:

1. Threshold for small partitions

   • Use Insertion Sort when the subarray size is below a fixed threshold (e.g., 16 elements).

2. Recursion depth monitoring

   • Track recursion depth as 2 * log2(n).
   • If the depth limit is reached, switch to HeapSort to avoid QuickSort’s worst-case.

3. Partitioning

   • Use a QuickSort partitioning scheme (Lomuto/Hoare).

4. Driver function

   • A wrapper introSort() that initializes the depth limit and calls the recursive utility.

5. Testing

   • Add test cases in main() to validate correctness.
   • Verify on best case, average case, and worst case inputs.

The final file will be named intro_sort.cpp under the sorting/ directory, following the style of existing algorithms.

Kindly assign me this issue so that I can start working on it.