x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 967

# Sorting alogorithm

Please tell me which sorting algorithm is most efficient when the data:
1. has very few unique elements
2. is in reverse sorted order.

Also, please tell me the complexity in each case.

Thanks!
0
dshrenik
1 Solution

Commented:
Come on. This is homework. Go read up on Big O notation and binary trees. 20 minutes of light reading and you should be able to figure this out.

Here: http://warp.povusers.org/SortComparison/
0

Commented:
http://en.wikipedia.org/wiki/Sorting_algorithm

If you need more detailed info you will have to provide sample data or more information.
The question sounds a bit like an exam or homework question.  if this is the case you are supposed to specify that.
0

Author Commented:
Its not a homework problem. I'm preparing for an interview.
I'm trying to identify the best algorithm for various scenarios:
When values are in a small range - Bucket sort
Nearly sorted - Insertion sort, etc.
0

Commented:
As above the links tell you all there is to know about sorting.   The formulas give you the rough time / memory / number of steps it takes to sort the field as the size etc increases.
You need to understand the idea of things like 'the big O'
If you understand that and you are able to code the basic sort functions then you can talk about it in an interview.
0

Commented:
If it's in reverse sorted order, then just flipping it is best. Time complexity is O(n). You could implement some kind of 'groupsort' than keeps all the same elements together.
For the traditional algorithms, you won't get better than O(nlg(n)) anyway. But if you do 'groupsort' you could get O(n + mlg(m)) where m is the number of unique elements.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.