Quicksort Algorithm Efficiency

Your title specifically lists efficiency as being significant.

If someone were to call your sort as:

List<integer> values = new LinkedList<>();
values.addAll(........);
sort(values, 0, values.size() - 1);

Then your sort would be horribly slow.

The reason is that these lines:

    Collections.swap(arr, i, j);
.....
Collections.swap(arr, i, right);

are not efficient when it comes to Linked Lists. Those lines would require a scan of the entire list because LinkedLists are not suited for high-performance random access. An ArrayList would be fine.... but, you don't always have an Arraylist

Additionally, note that there is no reason why you have to fix the Generic type at <Integer>. You force your comparator to do an "auto-unbox" of the values here:

int v = arr.get(right);     

and also in the arr.get(...) calls in the checks.

If you change your method signature to be a generic method like:

public static <T extends Comparable<? extends T>> void sort(List<T> arr, int left, int right)

Then you will be able to use the compareTo methods for comparisons.... like:

    T valus = arr.get(right);     

    for(;;) {
        while(value.compareTo(arr.get(++i)) >= 0);
        while(value.compareTo(arr.get(--j)) < 0 && j != 0)

Note, now that I am looking at the code more carefully, I see some problems in there.....

1. Your method will do odd things if there are duplicate values in the input... right? You need a <= or >= somewhere. I put it on the first loop.
2. you do not handle null values in the input (nor do I).

int i = left - 1;
int j = right + 1;
if (right - i == 0 || right - i == 1) return;

This might be right.. or left, or i, but is there a quick way to sort it out? To understand it, I must back-substitute i, assume which of your bounds are inclusive (lets hope, "left" included, "right" excluded as with Arrays.sort?), and rewrite it as

int length = right - left;
// right - i == length + 1
if (length == -1 || length == 0) return;

but I'd expect something like

if (length <= 1) return;

which needs no comment as there's obviously nothing to sort.

Your condition is different and that's either wrong or you interpret the inputs differently.

You don't have to document like this, but the bare minimum is

Sort the array from left (included) to right (excluded).

I'm sure this will blow performance to the land where bubble-sort lives whenever you start with a sorted sequence:

int v = arr.get(right);     

Let's call v threshold or pivot.

Duck Typing QuickSorts

Tony Hoare's QuickSort was considered quick in 1962. But it was not because it has 0(n log n) average performance. Merge sorting was already established [Knuth credits Von Neumann in 1945] and has better worst case performance than QuickSort.

What made QuickSort a quick sort was it's space efficiency. Hoare's insight was in-place sorting. QuickSort was quicker because in-place sorting meant more blocks could be read from tape into fast memory on each IO cycle [and likewise written]. The speed improvement came from reduced latency. Because IO then as now was so much slower than fast memory, the practical performance improvement on non-trivial data was massive.

It's common to illustrate functional programming using a double filter for the pivot and to call it a "quicksort". These necessarily avoid inplace mutations.

Consider this page of examples in Python. If you consider the Python examples to be quicksorts, then clearly the code under review is a quicksort. If you don't then...

Garbage Out

Because the Java manages memory deallocation via garbage collection; because the JVM offers just-in-time compilation that may perform arbitrary optimizations of the bytecode, and different ones at different times based on how much time it has due to what else is running; and because modern CPU's utilize multiple levels of caching, simple definitions of "in place" become increasingly brittle the more absolute our definition of "true quicksort" becomes. Welcome to the effects of post modernism in computing.

Practical Improvement

Issues of truth aside, the performance of QuickSort degrades toward worst case 0(n^2) if the data is sorted in reverse order. Hoare advised selecting the pivot at random rather than sequentially. That is randomly selecting the pivot from the interval [i, j] makes worst case performance statistically unlikely for any interestingly sized data. Of course, if the data source is known to be random then it's a waste of time. On the other hand, in the real world many data sources aren't random.

Final Remarks

There are many sound insights in the other code reviews, and there's no point in chewing the same ground.