Let’s say we have an unsorted array of a million integers and need these integers 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 two representative methods for duplicate removal (or known as DeDup or DeDuplicate).

The following C++ code shows a sort-unique method implementation:

std::sort(array_with_dups.begin(), array_with_dups.end());
auto dups_start = std::unique(array_with_dups.begin(), array_with_dups.end());
//array_with_dups.erase(dups_start, array_with_dups.end());

The third line (.erase) is optional, in case the resulting array needs to be shrunk down to only hold unique values.

And, here is C# code showing a hash set method implementation:

HashSet<int> set = new HashSet<int>(array_with_dups);
int[] uniqueArray = new int[set.Count];
set.CopyTo(uniqueArray);

The attributes of these two representative methods are summarized in the following table.

If memory space is tight, then O(nlgn) worst-case performance is the best in-place currently possible. If memory space is plentiful, or when stability is needed, then O(n) average-case performance is possible, with O(n²) worst-case lurking even at low probability.

A Linear Time In-Place Solution

Current methods are all comparison-based, which compare array elements to the each other. Sorting uses the “less then” comparison, while HashSet uses “equality” comparison. Using comparisons restricts performance for duplicate removal methods which use sorting to O(nlgn), whether in-place or not. Sorting can be in-place or not, while HashSet requires O(n) extra space – i.e. not-in-place.

Another way to remove duplicates is to use the sort-unique method, with a linear-time sorting algorithm, such as Radix Sort. Radix-based algorithms 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 have O(n) worst-case performance. Radix Sort is the fastest performing sort on GPUs and CPUs.

Applying Radix Sort to the remove duplicates has the potential to improve performance substantially. For instance, using an in-place MSD Radix Sort, enables O(n) in-place duplicate removal. In this case, within the a sort-unique method, sorting is in-place and the unique algorithm is also in-place. Both MSD Radix Sort and the unique algorithms are linear time. Thus, the overall algorithms is O(n) – i.e. linear time in the worst case performance.

The following C# code shows a sort-unique Radix-based implementation:

SortRadixMsd(array_with_dups);
Unique(array_with_dups);

Both functions are available in the C# HPCsharp open source nuget package, along with a DeDuplicate function that puts them together. This capability will be extended for many numeric data types, such as floating-point and user-defined types with numeric keys, and including strings in the future, since SortRadixMsd() support all numeric data types, except for C# Decimal data type.

Performance Measurements

The following Table shows performance of various duplicate removal algorithms for an array of 10 million random 32-bit integers, with around 15 thousand duplicates in C# and around 12 thousand duplicates in C++:

C++ provides a standard std::unique function. C++ In-Place MSD Radix Sort and LSD Radix are implemented in the ParallelAlgorithms repository. C# Unique function is a recent addition to the HPCsharp nuget package.

Conclusion

For duplicate removal, theoretical performance has been improved from O(n) on average while not-in-place, to O(n) worst-case while in-place, or to O(n) worst-case while not-in-place. The possibility of O(n²) has been eliminated.

Practical performance is significantly faster for C# and C++, from 2X to over 200X. Radix Sort is capable of supporting all numeric key data types as well as strings and user defined data types (see HPCsharp nuget repository for C# and ParallelAlgorithms repostory for C++ implementations).

Stability

Stability is not necessary for arrays of numeric or string keys, since there is no way to tell duplicate array elements apart. Stability comes into play when array elements have other data besides the keys being sorted by.

Stability of the algorithms is listed in the Tables above. In-Place MSD Radix Sort, Array.Sort, std::sort and std::set are not stable, and will not return the same duplicate array element if array size changes or other array elements change. C++ std::unordered_set, LSD Radix Sort are stable. This may not be important for some use cases, but for others it may be critical.

However, for removing duplicates, stability may not matter in some use cases, unless we care enough to only keep the first duplicate and discard all others, or want to keep a specific duplicate. For the case of not caring which duplicate is kept in the resulting unique array, an unstable Sort or HashSet algorithm could be used.