Kaustubh G Sharma wrote:In Java we do perform sorting using comparable or comparator interfaces and for similar objects it can be done by Collection.sort() method. I wanted to know, for say if we have 5 objects to sort, how many comparison will going to take place? is it !n or !n-1. also wanted to know, is there any default implementation of compareTo and compare methods? if so what algorithm is used by it and how to compression of objects take place?
This can't be answer exactly -- certainly not if the question is "is it N or N-1 comparisons?", meaning specific to an exact count. From the JavaDoc, the algorithm is a modified merge sort. And for those who studied what a merge sort is, it has an order of "N Log N", but ...
1. "N Log N" is only the complexity. It may be relative to the number of comparisons, and even then, it makes the assumption that N approaches infinity. So, you can get a relative scale, but not really an exact count.
2. With the merge sort, the "N Log N" is only a cap. It is actually data dependent. I believe merge sort needs less comparisons for a set of data that is more "sorted" than a completely random set of data.
3. The modified part of the merge sort will actually cause more comparisons, but depending on the result of the comparison, it may actually cause less comparisons. In other words, a more sorted set of data may trigger short cuts which may need less comparisons.
Henry