Member Search
|
|
Search
|
Watch Thread | My Post History | My Watches | User Settings View: Flat (newest first) | Threaded | Tree Previous Thread | Next Thread |
||
Forums
Tutorial Discussions
Sorting Tutorial
merge sort versus quick sort in Java
|
||
| merge sort versus quick sort in Java | Reply | |
| Hi, Is there a good reason why Java uses quick sort to sort primitive types while it uses merge sort to sort Objects? thanks, David |
|
| Re: merge sort versus quick sort in Java (response to post by dskloet) | Reply | |
| I'm guessing it's stability. If you're sorting primitives, then the ordering of values that compare as equal doesn't matter since they are the same. But if you're sorting objects, they may not use all the information in the object to determine sort order, and you might want objects that compare as equal using the compareTo or compare methods to stay in the same order they were in before sorting. | |
| Re: merge sort versus quick sort in Java (response to post by aussie) | Reply | |
| That must be it. I was thinking quick sort is stable as well but it isn't. | |
| Re: merge sort versus quick sort in Java (response to post by dskloet) | Reply | |
| I believe that it is because mergesort is fastest for sorting with pointers, linked list,etc. . Because objects are basically treated as pointers(thats why they are being passed by reference), Java must be using mergesort for better performance. Here's an excerpt from wikipedia: "Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible." regards |
|
| Re: merge sort versus quick sort in Java (response to post by kolistivra) | Reply | |
| Merge sort is often the best choice for sorting a linked list. I believe dskloet was talking about arrays, where random access performance has O(1) complexity. And I also believe that all operations that can be done on a primitive data type in Java has the same performance for pointers. That is because, pointers in Java have a fixed size. i.e.: They can copied, swapped and stored in arrays as they are some integers. Moreover, an array of objects in Java is just an array of pointers, which can be easily sorted (In a totally different place in the memory by any type of sort) if the comparison function was defined between those two memory addresses. My first guess was something different. Merge sort is O(n lg n), where Quick sort is a fast randomized algorithm but it is O(n^2) not O(n lg n). And in objects, no much assumptions could be taken. But that intuitively contradicts with the fact that C++ sort is Quick sort. |
|
| Re: merge sort versus quick sort in Java (response to post by mohamedafattah) | Reply | |
| What do you mean by "C++ sort is Quick sort"? If you are talking about sort() in STL, specification says only that it performs O(n log n) comparisons in the worst case. Furthermore, quoting the SGI docs on their STL implementation: The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average. |
|
| Re: merge sort versus quick sort in Java (response to post by misof) | Reply | |
| Awesome! Sorry for spreading out incorrect information. But I was told that C++ STL sort() is a quick sort, and I directly believed that :D. However, as I never heard about introsort, I read about Sorting algorithms in Wikipedia and I discovered also some nice sort algorithms that I didn't know before. |
|
| Re: merge sort versus quick sort in Java (response to post by mohamedafattah) | Reply | |
| Follow up response to an old thread. To clarify performance issue, even though the key issue is stability. Merge sort on objects is primarily done for stability, but it's also usually faster. In terms of performance, merge sort does more moves but fewer compares than quick sort or a variation of quick sort like intro sort. In the case of an array of pointers to objects, typically only the pointers are moved, while comparing objects requires dereferencing via the pointers, increasing the overhead for compare. The end result is merge sort is usually faster at sorting an array of pointers to objects than quick sort or a variation of quick sort. |
|
|
Forums
Tutorial Discussions
Sorting Tutorial
merge sort versus quick sort in Java
Previous Thread | Next Thread |
 |