Why is my mergesort slower than my quicksort?
They're both the same time complexity but when I run my merge sort on a randomly generated linked list with 100,000 entries:
public LinkedList<Integer> linkedListSort(LinkedList<Integer> list) {
if (list.size() <= 1) return list;
LinkedList<Integer> left = new LinkedList<Integer>();
LinkedList<Integer> right = new LinkedList<Integer>();
int middle = list.size()/2;
for (int i = 0; i < middle; i++) {
left.add((int)list.get(i)); steps++;
}
for (int i = middle; i < list.size(); i++) {
right.add((int)list.get(i)); steps++;
}
left = linkedListSort(left);
right = linkedListSort(right);
return merge(left, right);
}
public LinkedList<Integer> merge(LinkedList<Integer> left, LinkedList<Integer> right) {
LinkedList<Integer> result = new LinkedList<Integer>();
while (!(left.isEmpty()) && !(right.isEmpty())) {
steps++;
if ((int)left.peekFirst() <= (int)right.peekFirst()) {
result.add(left.poll());
} else {
result.add(right.poll());
}
}
while (!(left.isEmpty())) {result.add(left.poll()); steps++;}
while (!(right.isEmpty())) {result.add(right.poll()); steps++;}
return result;
}
It's a lot slower than my quick sort which is:
public String arraySort(int[] array, int startIndex, int endIndex, int steps) {
int leftIndex = startIndex;
int rightIndex = endIndex;
int pivot = array[(leftIndex + rightIndex) / 2];
while (leftIndex <= rightIndex) {
steps++;
//search for an element with a higher value than the pivot, lower than it
while (array[leftIndex] < pivot) {steps++; leftIndex++;}
//search for an element with a lower value than the pivot, higher than it
while (array[rightIndex] > pivot) {steps++; rightIndex--;}
//check the left index hasn't overtaken the right index
if (leftIndex <= rightIndex) {
//swap the elements
int holder = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = holder;
leftIndex++; rightIndex--;
}
}
if (leftIndex < endIndex) arraySort(array, leftIndex, endIndex, steps);
if (rightIndex > startIndex) arraySort(array, startIndex, rightIndex, steps);
return "Quicksort on an unsorted array took " + steps + " steps.";
}
What's the reason for this? Is my quicksort/mergesort not what it should be or is it that mergesort performs badly on a linked list with a large amount of random numbers? Or something else?
Thanks!
You've implemented a version of quicksort that's doing everything "in-place" while your mergesort copies the content of left/right upon every recursive call (and same thing with merge() ). That's probably the major reason for the differences.
Second, like Luiggi mentioned in the comments above - how do you do your benchmarking ? do you get a proper JVM warmup? do you run enough cycles and take average ? proper benchmarking with the JVM can be tricky: if you don't have experience with it, better look for a micro-benchmarking framework and use it!
链接地址: http://www.djcxy.com/p/31584.html