Introduction

Radix sort is a sorting algorithm that sorts elements by grouping them based on their digits. It is a non-comparative sorting algorithm that is faster than many other sorting algorithms, including the default std::sort function in C++. In this blog post, we will explore how radix sort works and how to implement it in C++.

How Radix Sort Works

In radix sort, we sort elements based on their digits, starting from the least significant digit to the most significant digit. We group the elements based on each digit and sort them accordingly. This process is repeated for each digit until all digits have been considered. The result is a sorted list of elements.

Implementing Radix Sort in C++

/// In the name of God the most beneficent the most merciful

#include <bits/stdc++.h>
using namespace std;

template<const bool negative = true, const int BITS = 9, typename _RandomAccessIterator>
inline void radix_sort(_RandomAccessIterator _first, _RandomAccessIterator _last, const bool reverse = false)
{
	typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
	if(negative)
	{
		if(!reverse) {
			_RandomAccessIterator _middle = partition(_first, _last, [](value_type a) -> bool {return a<0;});	
			for(auto it = _first; it != _middle; it++)*it *= -1;
			radix_sort<false>(_first, _middle, true);
			for(auto it = _first; it != _middle; it++)*it *= -1;
			radix_sort<false>(_middle, _last);
		} else {
			_RandomAccessIterator _middle = partition(_first, _last, [](value_type a) -> bool {return a>=0;});	
			radix_sort<false>(_first, _middle, true);
			for(auto it = _middle; it != _last; it++)*it *= -1;
			radix_sort<false>(_middle, _last);
			for(auto it = _middle; it != _last; it++)*it *= -1;
		}
		return;
	}
	constexpr int PART = (1<<BITS);
	constexpr int FULL = (1<<BITS)-1;
	int shift = 0;
	auto MAX = *max_element(_first, _last);
	vector<value_type> P[PART];
	while(log2(MAX) >= shift)
	{
		for(auto it = _first; it != _last; it++)P[(((*it)>>shift)&FULL)^(reverse?FULL:0)].push_back(*it);
		auto it = _first;
		for(int i = 0; i < PART; i++)
		{
			for(auto u: P[i]) *it++ = u;
			P[i].clear();
		}
		shift += BITS;
	}
}

int main() {
    vector<int> v{-3, 2, 3, -4, 1};
    radix_sort(v.begin(), v.end());
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

In this implementation, we first check if the input values are negative. If they are, we convert them to positive values, sort them, and then convert them back to negative values. We then loop through blocks of digits, starting from the least block, and sort the elements based on that block. We use a counting sort algorithm to sort the elements based on each block.

Performance Benchmarks

To compare the performance of radix sort with other sorting algorithms, we ran a benchmark test on several arrays of integers. Here are the results:

As you can see, radix sort is faster than the default std::sort function in C++ for most of the test cases.

Conclusion

Radix sort is a powerful sorting algorithm that can be used to sort elements faster than many other sorting algorithms. In this blog post, we explored how radix sort works and how to implement it in C++. We also compared the performance of radix sort with other sorting algorithms and found that it is faster than the default std::sort function in C++ for most test cases. I hope this blog post has been helpful to you!

You can find the source code and every things on https://github.com/Mohammad-Parsa-Elahimanesh/Radix-sort-Cpp.

If you have any opinion or criticism or if the code can be improved in terms of beauty or functionality, I would be very grateful to say it in the comments.

at end thanks Bing Ai to help me write this blog.

I hope to be useful for you!