Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Just wondering why Java and .NET Framework uses different sorting algorithm by default.

In Java Array.Sort() uses Merge Sort algorithm by default and as Wikipedia.com says:

In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted

In .NET Framework Array.Sort/List.Sort() uses Quick Sort as default sorting algorithm (MSDN):

List.Sort() uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

By looking at the great "Comparison of algorithms" table we can see that both algorithms has pretty different behaviour from Worst Case and Memory Usage perspectives:

enter image description here

Both Java and .NET are great Frameworks for Enterprise Solutions development, both has platforms for embedded development. So why they are using different sorting algorithm by default, any thoughts?

share|improve this question
1  
For further discussion on a comparison between these two sorts, see stackoverflow.com/q/680541/866022 –  Jim Sep 15 '11 at 20:17

3 Answers 3

up vote 9 down vote accepted

As deterministic as computers themselves are, computer engineering is not an exact science. Two people, given the same problem domain, will perform an analysis and develop two different solutions that satisfy all constraints of the problem. It may be difficult or impossible to empirically determine which of these is "better" in the general case.

My guess is that the .NET QuickSort is layered on top of something in the MFCs or Windows API, and is probably inherited from much older versions of Windows where the multi-threadable advantage of MergeSort wouldn't have even been considered for the computers of the day. Java, which can't use Microsoft's implementation because Java was designed from scratch to be platform-independent, went a different way. Who knows why MergeSort came out on top; my wild guess is that the implementation won some sort of performance competition versus some other sorts the developers came up with, or else that an O(n)-space MergeSort just looked best on paper in terms of best-case and worst-case performance (MergeSort has no Achilles' heel relating to element selection like QuickSort, and its best-case is a near-sorted list while that's often QuickSort's worst). I doubt multithreading benefits were initially considered, but the current implementation may well be multithreaded.

share|improve this answer
    
List<T>.Sort in .NET uses a native method implemented in the CLR (if you do not use a custom comparer), but has no dependencies on OS libraries. –  Joey Jun 18 at 15:50

Different development teams in two different companies came to different conclusions regarding the usual use case for their frameworks and components and have decided to implement accordingly.

Essentially, each company did their analysis, looked at their client base and made different decisions accordingly.

You can't expect analysis by different companies and teams, using different assumptions and raw data to come to the same conclusion.

share|improve this answer
5  
Or even the same assumptions and raw data . . . –  Wyatt Barnett Sep 15 '11 at 20:57

This question is a bit out of date, since Java now uses Timsort (as of Java 7)

Of the specific algorithms mentioned:

  • Quicksort has unfavourable worst-case performance at O(n^2), but is a bit more lightweight / less memory-consuming so offers better performance in a typical case.

  • Mergesort has guaranteed worst-case performance at O(n log n), but carries a bit more overhead and memory requirements. It is also automatically stable (i.e. maintains equal elements in the same order).

The Java designers seem in general to be a bit more conservative / focused on the "right thing" so it's not surprising that they chose Mergesort out of the two since it offers better guarantees.

Not sure why Microsoft chose Quicksort, maybe they though it would make them look better in some micro-benchmarks?

share|improve this answer
1  
Very good point, thanks for your answer!!! –  sll Sep 30 '11 at 10:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.