Sorting Algorithms

I did not remember when the last time I implemented sorting functions by myself was. Or I had never implemented sorting functions...

I use standard libraries for sorting problems. The sorting functions that standard libraries provide are working well for me so far.

Occasionally, I could not keep up with the conversation that others have talked about which sorting algorithm is better. At job interviews, sometimes interviewers have asked me about that, and I could not answer that. I read a few algorithm books, and I listened carefully to others talking about sorting algorithms.
I have some ideas about sorting algorithms. However, my understanding was bad since I had never been interested in it. Finally, I got the time and motivation to clear it out. It was fun learning the sorting algorithm. In addition, I am glad that I became a bit more familiar with C++.

Since there are so many articles and lectures about sorting algorithms, I do not write details of sorting algorithms here.

Comparison of algorithms

Wikipedia was helpful for me to check what kind of sorting algorithms exists.
The tables were helpful, and it was easy to use.

Sorting algorithm - Wikipedia

How to pick a sorting algorithm

Their "complexity and stability" should be considered. The same "time complexity" does not mean the same performance.
For example, the best and average time complexities of Quicksort and Heapsort are the same. Heapsort has better worst-case time complexity and memory usage than Quicksort. In practice, Quicksort is faster than Heapsort.

Comparing Quick and Heap Sorts
Why is quicksort better than other sorting algorithms in practice?

Non-comparison sorts

A comparison sort cannot perform better than O(n log n) on average.
Non-comparison sorting algorithms are not limited to O(n log n).

Radix Sort

Among non-comparison sorts, I was intrigued by Radix Sort. Many examples of Radix Sort I could find are for integer sorting. I was wondering if it can be used for other typed values. I found very interesting articles via a Stackoverflow answer. The following pages explain how to use Radix Sort for float values.

Radix Sort Revisited : Pierre Terdiman (published in 2000)
Radix Tricks : Michael Herf (published in December 2001)

I ran Michael Herf's Radix Tricks code. For the first time, I did not understand. I kept reading the page several times and I researched what I needed to know to fully understand. To fully understand what he mentioned on the page, I needed to understand basic C++ syntax and IEEE Standard for Floating-Point Arithmetic (IEEE 754).

Single-precision floating-point format

I finally understood why float values can handle huge numbers, and it does not work the same as decimal values. While I was figuring out Radix Trick, I often thought of a bitwise operation. I used to have immediate rejection for bitwise operations. It was not as bad as I feared. I might need a little more time to be comfortable with it.

Will I ever implement sorting functions by myself?

After learning some sorting algorithms, I was wondering if I would ever implement them by myself. The same as other people's thoughts I have found, I would probably not. After researching what sorting algorithms the standard libraries use, I understood they are already well-optimized. Even if standard libraries do not provide sorting functions with some algorithms, there is a high chance that we can find open-sourced ones. Since lots of open-sourced projects are available nowadays, it must be difficult to come up with a better implementation by myself.

There are interesting discussions while seeking what other people think.
Programming by poking: why MIT stopped teaching SICP
Hacker News
Reddi

I was thinking if I had known sorting algorithms and the products I have worked on would have been a lot better. It could be better but not a lot.

Learning algorithms give me some joy and confidence. I appreciate those who came up with algorithms. I want to keep learning algorithms.