Search code examples
algorithmsortingunique

Which order of sort and unique is faster?

For example in Julia

julia> sort(unique([1,2,3,2,1]))
3-element Array{Int64,1}:
 1
 2
 3

julia> unique(sort([1,2,3,2,1]))
3-element Array{Int64,1}:
 1
 2
 3

Which order is faster? And why?

Solution

  • According to the docs, Julia uses QuickSort as default for the numeric input. This is a n log n operation.

    Unique takes complextity of O(n) both time and space.

    Now, consider a small input of 10000 numbers.

    Case 1: Let say only 1000 of these are unique.

    Suppose you run sort(unique(arr)) then you would basically be sorting only 1000 numbers compared to unique(sort(arr)) where you would sort 10000 numbers.

    Case 2: Let say all 10000 of these are unique. Now, here there is no significant change in the performance between the two as the sort function takes all the 10000 values either way.

    So, it totally depends on input. But it makes sense to use sort(unique(arr)).