What is wrong with my Java quicksort implementation?

I'm pretty sure I understand how quicksort works, but I can't find the bug that's causing my attempt at implementing it to not work. I've looked through this for 开发者_如何学Chours and can't figure out what's wrong. Please help me! Here is the entire file (It's just quicksort - nothing extra. The array is just random numbers for testing the quicksort.)

public class Quicksort{ 

    public static void main(String args[]){
        int[] arr = {5,1,4,3,7,0,9,2,6,8};
        quicksort(arr, 0, arr.length-1);
        for(int x : arr)
          System.out.print(x+" ");
    }

    public static void quicksort(int[] arr, int start, int end){
        if(end-start<2)
            return; 
        int pivot = (end-start)/2;
        int i = start; 
        int k = end;
        while(k>i){
            while(arr[i]<arr[pivot]&&k>i&&i<=end)
                i++; 
            while(arr[k]>arr[pivot]&&k>=i)
                k--; 
            if(k>i){
                swap(arr, i, k); 
            }
        }
        swap(arr, pivot, i);

        quicksort(arr, 0, i);
        quicksort(arr, k, arr.length-1);
     }

     public static void swap(int[] a, int x, int y){
         int temp = a[x]; 
         a[x] = a[y]; 
         a[y] = temp; 
     }
}

As it is right now, the loop never terminates... it's a forever infinite loop! Please help me figure out what's wrong.

Do yourself a favor and learn how to use a debugger. It makes solving this kind of problems very easy.

Your base case should be if(end-start<1) - You only want to stop sorting when the number of elements is 1 (i.e. if start and end are equal)

Your while loops should just be while(arr[i]<arr[pivot]) and while(arr[k]>arr[pivot])

This

if(k>i){
    swap(arr, i, k); 
}

should be

if(k>=i){
    swap(arr, i, k);
    i++;
    k--;
}

swap(arr, pivot, i); is unnecessary.

Your recursive call should be quicksort(arr, start, k); and quicksort(arr, i, end);

Couple of things that stand out --

1. Your end condition seems incorrect. If your array has just 2 elements, it won't sort them.

2. Also, after you do the swap, you need to increment and i and decrement k.

while(arr[i]<arr[pivot]&&k>i&&i<=end)

Clearly you have had array index problems. All these tests aren't required in a working Quicksort, and the ones that are are in the wrong order.