StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POQuicksort slower than Mergesort?
text
Body
copied!<p>I was working on implementing a quicksort yesterday, and then I ran it, expecting a faster runtime than the Mergesort (which I had also implemented). I ran the two, and while the quicksort was faster for smaller data sets <100 elements (and I <i>did</i> verify that it works), the mergesort became the quicker algorithm fairly quickly. I had been taught that quicksort is almost always "quicker" than mergesort, and I understand that there is some debate on this topic, but I at least expected it to be closer than this. For data sets >10000 elements, the mergesort was over 4 times faster. Is this to be expected, or is there an error in my quicksort code?</p> <p>mergesort:</p> <pre><code>public static void mergeSort(int[ ] e) { if (e.length <= 1) return; int[] first = new int[e.length/2]; int[] second = new int[e.length - first.length]; System.arraycopy(e, 0, first, 0, first.length); System.arraycopy(e, first.length, second, 0, second.length); mergeSort(first); mergeSort(second); System.arraycopy(merge(first, second), 0, e, 0, e.length); } private static int[] merge(int[] first, int[] second) { int iFirst = 0; int iSecond = 0; int iCombined = 0; int[] combined = new int[first.length + second.length]; while(iFirst < first.length && iSecond < second.length) { if (first[iFirst] > second[iSecond]) { combined[iCombined++] = second[iSecond++]; } else combined[iCombined++] = first[iFirst++]; } for(; iFirst < first.length; iFirst++) { combined[iCombined++] = first[iFirst]; } for(; iSecond < second.length; iSecond++) { combined[iCombined++] = second[iSecond]; } return combined; } </code></pre> <p>quicksort:</p> <pre><code>public static void quicksort(int[] a, int first, int last) { if (first >= last) return; int partitionIndex = partition(a, first, last); quicksort(a, first, partitionIndex - 1); quicksort(a, partitionIndex + 1, last); } public static int partition(int[] x, int first, int last) { int left = first; int right = last; int pivot = x[first]; int pivotIdx = first; while(left <= right) { while(left < x.length && x[left] <= pivot) left++; while(right >= 0 && x[right] > pivot) right--; if (left <= right) { int temp = x[left]; x[left] = x[right]; x[right] = temp; } } pivotIdx = right; x[first] = x[right]; x[pivotIdx] = pivot; return pivotIdx; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload