Sorting an ArrayList of Vehicles using quick sort For an assignment I have to sort an ArrayList of Vehicle objects using the quick sort method. I have come up with two implementations for this, which would be the best to use? Is method 1 considered quick sort since it splits the array? 

Method 1

protected ArrayList&lt;Vehicle&gt; quickSort(ArrayList&lt;Vehicle&gt; list)
{
    if (list.size() &lt;= 1) 
        return list; // Already sorted  

    ArrayList&lt;Vehicle&gt; sorted = new ArrayList&lt;Vehicle&gt;();
    ArrayList&lt;Vehicle&gt; lesser = new ArrayList&lt;Vehicle&gt;();
    ArrayList&lt;Vehicle&gt; greater = new ArrayList&lt;Vehicle&gt;();
    Vehicle pivot = list.get(list.size()-1); // Use last Vehicle as pivot
    for (int i = 0; i &lt; list.size()-1; i++)
    {
        //int order = list.get(i).compareTo(pivot);
        if (list.get(i).compareTo(pivot) &lt; 0)
            lesser.add(list.get(i));    
        else
            greater.add(list.get(i));   
    }

    lesser = quickSort(lesser);
    greater = quickSort(greater);

    lesser.add(pivot);
    lesser.addAll(greater);
    sorted = lesser;

    return sorted;
}


Method 2

protected ArrayList&lt;Vehicle&gt; quickSort(ArrayList&lt;Vehicle&gt; list, int a, int b)
{
    if (a &gt;= b) 
        return list;

    Vehicle pivot = list.get(b);

    int left = a;
    int right = b;

    while (left &lt; right)
    {
        while(list.get(left).compareTo(pivot) &lt; 0)
            left++;

        while(list.get(right).compareTo(pivot) &gt; 0)
            right--;

        if (right &gt; left);
        {
            Collections.swap(list, left, right);
        }
    }

    quickSort(list, a, right-1);
    quickSort(list, right+1, b);

    return list;
}


Now the problem with Method 2 is that my protected quickSort is called from 

public ArrayList&lt;Vehicle&gt; quickSort()
{   
    return quickSort(vehicleList);
}


which I'm not allowed to modify, so I'd need to overload the method again and call my version with the two extra integer parameters. Would this just be messy doing another overload?
In method 1 the sorted list you create here:

ArrayList&lt;Vehicle&gt; sorted = new ArrayList&lt;Vehicle&gt;();


is never used and overwritten here:

sorted = lesser;


Just drop the variable sorted and return lesser.



There is no reason to limit the method to ArrayLists or even Vehicles. Just have Vehicle implement the standard Comparableinterface and let your method have the signature:

protected &lt;T extends Comparable&lt;T&gt;&gt; List&lt;T&gt; quickSort(List&lt;T&gt; list) {
  // ...
}