Skip to main content
Code Review

Return to Answer

added 78 characters in body
Source Link
Cedric
Cedric
  • 216
  • 1
  • 5

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).

Performance wise, it's hard to beat if you have a small range of value N.

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).

Performance wise, it's hard to beat if you have a small range of value N.

Source Link
Cedric
Cedric
  • 216
  • 1
  • 5

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your possible range of values is small (let's call it N) so you can just try all N values and it will be O( N ).