Quicksort in Java

Hier eine erste Implementierung von Quicksort, allerdings hat diese den Nachteil das ein StackOverflowError rasch erreicht wird:

package at.ande.sorting.quicksort;

import java.util.ArrayList;

public class QuickSort {
 
 ArrayList list;
 
 public ArrayList quickSort(ArrayList arraylist){
  list = arraylist;
  sort(0, arraylist.size() - 1);
  return list;
 }
 
 public void sort(int left, int right){
  if (left < right){
   int divisor = divide(left, right);
   sort (left, divisor - 1);
   sort (divisor + 1, right);
  }
  
 }
 
 public int divide(int left, int right){
  int i = left;
  int j = right -1;
  int pivot = list.get(right);
  
  do{
   while (list.get(i) <= pivot && i < right){
    i = i + 1;
   }
   while (list.get(j) >= pivot && j > left){
    j = j - 1;
   }
   if( i < j){
    int temp = list.get(i);
    list.set(i, list.get(j));
    list.set(j, temp);
   }
   
  } while (i < j );
  
  if(list.get(i) > pivot){
   int temp = list.get(i);
   list.set(i, list.get(right));
   list.set(right, temp);
  }
  return i;
 }
}

Ein Screenshot der Console des bei größeren Listen schnell auftretenden Fehlers:

Implementiert man Quicksort iterativ anstatt rekursiv funkt es auch mit großen Mengen: Iterative Implementierung von Quicksort
Quicksort von ungarischen Folkloretänzern getanzt

Links:
Ausführliche Seite über Quicksort