Let’s say we have an unsorted array of a million integers where all array elements need to be unique. We need a way to eliminate duplicates, which can occur anywhere within the array.

Current Solutions

Searching the internet, or asking AI, yields the following methods:

If memory space is tight, then Sort is the method of choice with O(nlgn) performance, which does not preserve the original array element order. If memory is available, and the worst-case performance is not a concern, then HashSet is the method of choice, with O(n) performance on average. However, the worst-case could show up, where it the HashSet could take “forever”.

A Better Solution

The above methods are all comparison-based, which compare array elements internally to the each algorithm. Using comparisons restricts performance.

Another way is to use Radix-based algorithms which do not compare array elements, but instead look at the digits or letters of the keys. Radix Sorts can be in-place or not-in-place, and are O(n) in performance. Radix Sort is the fastest sort on GPUs and CPUs. Applying Radix Sort to the remove duplicates has the potential to improve performance dramatically.

More details shortly… Along with performance benchmarks…