You could use a modified version of merge sort where if an element already exists you don't add it (you end up adding only unique elements), this will save the extra O(n) where you remove the duplicates.