Krdytkyu

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) {

            left.add(element);

        } else if (element > pivotalValue) {

            right.add(element);

        } else {

            pivotalValues.add(element);

        }

    }

    List<Integer> sortedLeft = sort(left);

    List<Integer> sortedRight = sort(right);

    sortedLeft.addAll(pivotalValues);

    sortedLeft.addAll(sortedRight);

    return sortedLeft;



}

What do you think about my implementation?

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.