20

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?

Improve this question
1

3 Answers 3

Reset to default
10

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. (EDIT: it's not, though Microsoft developers have been QuickSort fanboys for a long time, as evidenced by this choice of sorting implementation since MS-DOS).

Java, which can't use any platform-specific implementation because Java was designed from scratch to be completely 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.

Improve this answer
5
  • 1
    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, 2014 at 15:50
  • 1
    @Keith - .NET isn't layered on top of anything and was designed to be platform independent. You can see the implementation right here: github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/…
    – Robert MacLean
    Apr 10, 2015 at 10:26
  • @RobertMacLean - ".NET isn't layered on top of anything" is not a true statement, though you have demonstrated that the Sort function in question is wholly "managed" code. Large portions of .NET, including cryptography support, Windows desktop GUI libraries, Windows API interop (including process and threading control) are all based on pre-existing unmanaged code including the MFCs. They simply have to be; Windows itself has only a very minor .NET component of its codebase, the rest is unmanaged
    – KeithS
    Apr 17, 2015 at 22:26
  • It does remain that Microsoft devs are proven fanboys of QuickSort over other implementations, as QuickSort has been the algorithm of choice since MS-DOS, and this would have influenced their decision to implement .NET's sorting with this algorithm.
    – KeithS
    Apr 17, 2015 at 22:28
  • This answer is so wrong I am honestly shocked.
    – user9993
    May 12, 2018 at 12:12
18

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.

Improve this answer
2
  • 5
    Or even the same assumptions and raw data . . .
    – Wyatt Barnett
    Sep 15, 2011 at 20:57
  • Yeah it was probably just force of habit--microsoft was used to using the (unstable) quicksort, java wanted to go with the stable kind...and merge sort was the fastest known stable...
    – rogerdpack
    Jul 3, 2018 at 17:46
14

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?

Improve this answer
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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