Best Sorting Algorithms?

[rerrcatch]

🏷️ Discussion Type

Question

Body

Hey! I'm currently working on a rather simple project, @cxxalgo. It's a simple collection of algorithms/personal project, I'm trying to write pretty much just a bunch of algorithms with the scope of learning the best practices and their implementation in C++. I'm wondering, what do you consider the best general-use sorting algorithms? As of now I've only written quicksort and merge-sort. Feel free to check it out! Maybe contribute? Thank you all though!

Guidelines

• I have read and understood this category's guidelines before making this post.

[PhilterPaper]

Well, there is no "one best" sorting algorithm. Different ones may be best suited for different purposes and different languages. For very small data files, even a Bubble Sort may be best, as it has very little overhead. Quicksort is a classic, but have fun doing it in a language such as Fortran, with no recursion. Some sorts perform very well on almost-sorted data (such as adding one record to an already-sorted list), while doing horribly on a completely reverse-sorted input. It all depends.

[CoYildiz]

I agree with you except Bubble Sort part. I haven't seen this algorithm work anywhere. I think it is a myth.

[Mothukuri-venu]

There isn't really one "best" general-purpose sorting algorithm. In practice, the best choice depends on the data, whether stability is required, memory constraints, and the guarantees you need.

For a general-purpose C++ implementation, I'd look at these:

Introsort — probably the most important one to implement next. It starts with quicksort but switches to heapsort when recursion gets too deep, giving you quicksort-like performance while avoiding quicksort's worst-case O(n²). std::sort is typically implemented using an introspective/hybrid approach.

Merge sort — O(n log n) worst-case and stable, but requires O(n) additional memory for the usual array implementation.

Heapsort — O(n log n) worst-case and O(1) auxiliary space, but usually less cache-friendly than quicksort/introsort.

Insertion sort — absolutely worth implementing despite being O(n²). It's excellent for very small arrays and nearly sorted data, and is commonly used as the small-partition fallback inside faster hybrid sorts.

TimSort — particularly interesting if you want to learn how algorithms can exploit existing order in real-world data. It combines ideas from insertion sort and merge sort and is highly effective on partially sorted sequences.

Counting/radix sort — worth adding if you want to explore non-comparison sorting. For suitable integer/key domains, they can beat the comparison-sort O(n log n) lower bound.

I'd also slightly disagree with the idea that Bubble Sort is useful for small datasets. While it has low conceptual/implementation overhead, insertion sort is generally the more useful O(n²) algorithm in real implementations because it performs very well on small or nearly sorted ranges and has good cache behavior.

Since your goal is learning C++ algorithms and best practices, I'd suggest implementing them roughly in this order:

Insertion → Heap → Introsort → TimSort → Counting/Radix

You could then benchmark all of them against std::sort using random, sorted, reverse-sorted, nearly-sorted, and duplicate-heavy inputs. That would make the project much more interesting than simply collecting implementations, because you'd be able to see why there isn't a single best sorting algorithm.

i hope this answers will help u( @rerrcatch )

[mhmdwaelanwr]

There isn’t one “best” sorting algorithm for every case — it depends on the data and your requirements.

For general application code, the best choice is usually the language’s built-in sorting function because it is highly optimized and well tested.

A simple rule of thumb:

Nearly sorted data: insertion-sort-based or adaptive algorithms can perform very well.
Stable sorting required: merge-sort-style approaches are a good choice.
Guaranteed O(n log n) worst case with low extra memory: Heap Sort is useful.
Integer keys with a limited range: Counting Sort or Radix Sort can outperform comparison-based sorting.
General random data: Quick Sort / hybrid implementations are often very fast in practice.

So instead of asking “Which sorting algorithm is the best?”, I would choose based on:

input size,
whether the data is nearly sorted,
memory limits,
whether stability is required,
and what type of values are being sorted.

For production code, I would normally start with the built-in sort and only replace it after benchmarking a real workload.

[PhilterPaper]

In case you're not familiar with the concept of sorting "stability", it's whether two records with equal sort keys are guaranteed to appear in the same order every time. An "unstable" sort, such as Quicksort, can swap them around at random (since they have the same keys).