Why is my quick sort so slow?
- by user513075
Hello, I am practicing writing sorting algorithms as part of some interview preparation, and I am wondering if anybody can help me spot why this quick sort is not very fast? It appears to have the correct runtime complexity, but it is slower than my merge sort by a constant factor of about 2. I would also appreciate any comments that would improve my code that don't necessarily answer the question.
Thanks a lot for your help! Please don't hesitate to let me know if I have made any etiquette mistakes. This is my first question here.
private class QuickSort implements Sort {
@Override
public int[] sortItems(int[] ts) {
List<Integer> toSort = new ArrayList<Integer>();
for (int i : ts) {
toSort.add(i);
}
toSort = partition(toSort);
int[] ret = new int[ts.length];
for (int i = 0; i < toSort.size(); i++) {
ret[i] = toSort.get(i);
}
return ret;
}
private List<Integer> partition(List<Integer> toSort) {
if (toSort.size() <= 1)
return toSort;
int pivotIndex = myRandom.nextInt(toSort.size());
Integer pivot = toSort.get(pivotIndex);
toSort.remove(pivotIndex);
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
for (int i : toSort) {
if (i > pivot)
right.add(i);
else
left.add(i);
}
left = partition(left);
right = partition(right);
left.add(pivot);
left.addAll(right);
return left;
}
}
