Quicksort implementation with pivotal calculated as middle element

I read quick sort algorhitm and implemented in like this:

public List<Integer> sort(List<Integer> list) {
if (list.size() <= 1) {
return list;
}

int pivotalValue = list.get(list.size() / 2);

List<Integer> left = new ArrayList<>();
List<Integer> pivotalValues = new ArrayList<>();
List<Integer> right = new ArrayList<>();
for (Integer element : list) {
if (element < pivotalValue) {
} else if (element > pivotalValue) {
} else {
}
}
List<Integer> sortedLeft = sort(left);
List<Integer> sortedRight = sort(right);
return sortedLeft;

}


What do you think about my implementation?

• Once upon a time Niklaus Wirth said: "Algorithms + Data Structures = Programs". Your code is a nice example how forcing an algorithm on an inappropriate data structure leads to inefficient program. Quicksort is for arrays, not for lists. Use any kind of merge sorting for lists, they need less memory and are more bad-data-proof. Apr 24, 2019 at 11:21
• For comparison, you might want to look at a similar code review question I posted a while back: codereview.stackexchange.com/questions/226467/… Dec 20, 2019 at 3:07

What do you think about my implementation?

To tell you the truth, I don't think much of your implementation. Instead of in-place swaps you're creating a bunch of temporary lists and combining them after. It probably more closely resembles a merge sort than a quick sort.

Creating all those lists and merging them together requires many more iterations than the usual quick sort.

Altogether, it seems to me, that both the time and space complexity is worse than the usual quick sort.

• I am agree about memory complexity, but I don't understand why time complexity worse than usual quick sort Oct 25, 2018 at 17:22
• @gstackoverflow - merging the lists together requires extra iterations over the data.
– user33306
Oct 25, 2018 at 17:25
• Are you sure? lists are not arrays Oct 25, 2018 at 17:33
• @gstackoverflow - a quote from the addAll doc page The new elements will appear in this list in the order that they are returned by the specified collection's iterator.
– user33306
Oct 25, 2018 at 17:41
• @gstackoverflow re. I don't understand why time complexity worse than usual quick sort Did you test it? What kind of run time to you get? How does that compare to Collections.sort()? Dec 20, 2019 at 3:15