[FEATURE] Add implementation of Intro Sort #197

New Issue

claunia · 2026-01-29T15:08:26Z

claunia commented

2026-01-29 15:08:26 +00:00

Originally created by @R2-STAR on GitHub (Sep 30, 2025).

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 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

Possible Implementation

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

Threshold for small partitions
- Use Insertion Sort when the subarray size is below a fixed threshold (e.g., 16 elements).
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.
Partitioning
- Use a QuickSort partitioning scheme (Lomuto/Hoare).
Driver function
- A wrapper introSort() that initializes the depth limit and calls the recursive utility.
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.

Originally created by @R2-STAR on GitHub (Sep 30, 2025). ### 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 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 ### 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 ### 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.

claunia added the Stale enhancement labels 2026-01-29 15:08:26 +00:00

claunia closed this issue

2026-01-29 15:08:27 +00:00

claunia commented

2026-01-29 15:08:29 +00:00

@kokatesaurabh commented on GitHub (Oct 1, 2025):

Hi @R2-STAR,

I’ve completed the implementation of the IntroSort algorithm in C as described in this issue.
The introsort.c file includes QuickSort as the base, switches to HeapSort at the depth limit,
and uses InsertionSort for small partitions. All test cases have been verified and it’s working correctly.

You can review the PR for the full implementation.

@kokatesaurabh commented on GitHub (Oct 1, 2025): Hi @R2-STAR, I’ve completed the implementation of the IntroSort algorithm in C as described in this issue. The `introsort.c` file includes QuickSort as the base, switches to HeapSort at the depth limit, and uses InsertionSort for small partitions. All test cases have been verified and it’s working correctly. You can review the PR for the full implementation.

claunia commented

2026-01-29 15:08:30 +00:00

@github-actions[bot] commented on GitHub (Nov 1, 2025):

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@github-actions[bot] commented on GitHub (Nov 1, 2025): This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

claunia commented

2026-01-29 15:08:32 +00:00

@github-actions[bot] commented on GitHub (Nov 9, 2025):

Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!

@github-actions[bot] commented on GitHub (Nov 9, 2025): Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our [Gitter](https://gitter.im/TheAlgorithms) channel or our [Discord server](https://the-algorithms.com/discord/). Thank you for your contributions!

claunia referenced this issue

2026-01-29 15:13:04 +00:00

[PR #197] [CLOSED] Update README.md #467

claunia referenced this issue

2026-01-29 15:13:06 +00:00

[PR #197] Update README.md #472

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/C#197