[PR #1489] [FEATURE] Add implementation of IntroSort in C #2092

New Issue

claunia · 2026-01-29T15:28:35Z

claunia commented

2026-01-29 15:28:35 +00:00

Original Pull Request: https://github.com/TheAlgorithms/C/pull/1489

State: closed
Merged: No

This PR adds an implementation of the IntroSort (Introspective Sort) algorithm in C.

IntroSort is a hybrid sorting algorithm that combines QuickSort, HeapSort, and InsertionSort.
It begins with QuickSort, switches to HeapSort when recursion depth exceeds a certain limit,
and uses InsertionSort for small partitions. This ensures both fast average-case performance
and worst-case optimality. IntroSort is the algorithm behind std::sort.

Proposed Changes:

Add introsort.c with the full IntroSort implementation.
Use QuickSort as the base algorithm.
Switch to HeapSort if recursion depth exceeds 2 * log2(n) (bit-hack __builtin_clz used for log2).
Use InsertionSort for subarrays smaller than 16 elements.
Include helper functions: swap, heapify, printArray, and test cases in main().
Safe handling of empty and single-element arrays.
Inline comments detailing time and space complexity.

Benefits:

Adds a high-performance, practical sorting algorithm used in real-world systems.
Complements existing sorting algorithm collection in the repository.
Provides a reference implementation for hybrid sorting strategies.
Helps learners understand how QuickSort, HeapSort, and InsertionSort can be combined effectively.

Testing:

Verified correctness using multiple test cases: random, sorted, reverse-sorted, duplicate elements, single element, and empty array.
Prints original and sorted arrays for demonstration.

This implementation ensures IntroSort is easy to compile and run on any system without additional dependencies (math.h removed; log2 replaced with bit-hack).

Closes #1488.

**Original Pull Request:** https://github.com/TheAlgorithms/C/pull/1489 **State:** closed **Merged:** No --- This PR adds an implementation of the IntroSort (Introspective Sort) algorithm in C. IntroSort is a hybrid sorting algorithm that combines QuickSort, HeapSort, and InsertionSort. It begins with QuickSort, switches to HeapSort when recursion depth exceeds a certain limit, and uses InsertionSort for small partitions. This ensures both fast average-case performance and worst-case optimality. IntroSort is the algorithm behind std::sort. **Proposed Changes:** - Add `introsort.c` with the full IntroSort implementation. - Use QuickSort as the base algorithm. - Switch to HeapSort if recursion depth exceeds `2 * log2(n)` (bit-hack `__builtin_clz` used for log2). - Use InsertionSort for subarrays smaller than 16 elements. - Include helper functions: `swap`, `heapify`, `printArray`, and test cases in `main()`. - Safe handling of empty and single-element arrays. - Inline comments detailing time and space complexity. **Benefits:** 1. Adds a high-performance, practical sorting algorithm used in real-world systems. 2. Complements existing sorting algorithm collection in the repository. 3. Provides a reference implementation for hybrid sorting strategies. 4. Helps learners understand how QuickSort, HeapSort, and InsertionSort can be combined effectively. **Testing:** - Verified correctness using multiple test cases: random, sorted, reverse-sorted, duplicate elements, single element, and empty array. - Prints original and sorted arrays for demonstration. This implementation ensures IntroSort is easy to compile and run on any system without additional dependencies (`math.h` removed; `log2` replaced with bit-hack). Closes #1488.

claunia added the pull-request label 2026-01-29 15:28:35 +00:00

claunia closed this issue

2026-01-29 15:28:36 +00:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/C#2092