multithreaded quick sort does not give answer as expected

Question

I modified quick sort to make it multithread. I expected it to work , coz the original algorithm was working. After partitioning, for the recursive calls to left and right of pivot .. I am creating a new thread.

public class QuickSort extends Thread{
    private int[] arr;
    private int left;
    private int right;
public QuickSort(int[] arr){

    this.arr= arr;
    this.left=0;
    this.right=arr.length -1;
    this.start();
}

public QuickSort(int[] arr, int left , int right){

    this.arr= arr;
    this.left=left;
    this.right=right;
    this.start();

}

    int partition( int left, int right)
    {
          int i = left, j = right;
          int tmp;
          int pivot = arr[(left + right) / 2];

          while (i <= j) {
                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                      tmp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = tmp;
                      i++;
                      j--;
                }
          };

          return i;
    }

    void quickSort(int left, int right) {
          int index = partition(left, right);
          if (left < index - 1)
                new QuickSort(arr, left , index -1);
          if (index < right)
              new QuickSort(arr ,index, right);
    }

    public void run(){
        quickSort(left , right);
    }

    public static void main(String arg[])
    {
        int[] s = {100,99,98,97,96,95,94,93,92,91};
        new QuickSort(s);
        for(int i: s)
            System.out.println(i);
    }
}

Answer 1

Your first problem is that you aren't waiting for any thread to exit, so you are printing the data while the threads are still running. You need some Thread.join() calls.

I'm not saying there aren't other problems ... Your sort fails if there are already sorted elements, e.g. if you add 89,90 to your test array.