The below (incorrect) program enters an infinite loop.  When I run this program,
the IDE becomes unresponsive, and I need to kill NetBeans through the Windows
process manager.



package com.kitfox.util.datastruct;

import java.util.*;

/**
 * A quicksort algorithm that will sort very quickly and without allocating
 * additional memory an array that is already mostly sorted.
 *
 * Will also perform an O(n log n) quicksort on a regular list.
 *
 * http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
 *
 * @author kitfox
 */
public class Quicksort
{
    
    /** Creates a new instance of Quicksort */
    private Quicksort()
    {
    }
    
    public static <T extends Comparable<? super T>> void quicksort(List<T> list)
    {
        quicksort(list, 0, list.size() - 1);
    }
    
    /**
     * Quicksort elements of this list from lo to hi inclusive
     */
    public static <T extends Comparable<? super T>> void quicksort(List<T> list,
int lo, int hi)
    {
        //  lo is the lower index, hi is the upper index
        //  of the region of array a that is to be sorted
        int i = lo, j = hi;
        T pivot = list.get((lo + hi) / 2);
        
        //  partition
        do
        {
            while (i < hi && list.get(i).compareTo(pivot) <= 0)
            {
                i++;
            }
            while (j > lo && list.get(j).compareTo(pivot) >= 0)
            {
                j--;
            }
            if (i < j)
            {
                T ele1 = list.get(i);
                T ele2 = list.get(j);
                list.set(i, ele2);
                list.set(j, ele1);
                i++; j--;
            }
        } while (i <= j);
        
        //  recursion
        if (lo < j) quicksort(list, lo, j);
        if (i < hi) quicksort(list, i, hi);
    }
    
    public static void main(String[] args)
    {
        Vector<Integer> list = new Vector<Integer>();
//        for (Integer ival: new int[]{1, 5, 3, 9, 6, 0, 23, 7, 2, 3, 6, 7})
        for (Integer ival: new int[]{2, 3, 1})
        {
            list.add(ival);
        }
        
        quicksort(list);
        
        for (Integer ival: list)
        {
            System.err.print(" " + ival);
        }
    }
}