Selecting the Pivot from the median of three items QuickSort (JAVA)

Question

I have been working on one of my programs related to the implementation of Quick Sort. The code below is a quick sort algorithm that selects the median of three elements as the pivot. But the thing is that I am interested in selecting the first three elements of the array as the pivot and not the (lowest, middle, and highest indices of the sub-array). For example: If I have the numbers 5,85,65,4,75 in an array, I would be able to compare the first three elements in the array (5,85,65) in order to get the median which in this case is 65. I'd really appreciate any feedback on this matter.

public class QuickSort123
{

    public static void main(String[] args) 
    {
        int[] array = { 14, 9, 28, 3, 7, 63, 89, 5};

        // invoking methods
        printArray(array);
        sort(array);
        printArray(array);
    }

    public static void sort(int[] array)
    {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int low, int high)
    {

       if (low >= high)
       return;

       // Selecting the  pivot
       int middle = low + (high - low) / 2;
       int pivot = array[middle];

       while (low <= high) 
       {
            while (array[low] < pivot)
            {
                 low++;
            }

            while (array[high] > pivot) 
            {
                 high--;
            }

            if (low <= high)
            {
                 int temp = array[low];
                 array[low] = array[high];
                 array[high] = temp;
                 low++;
                 high--;
             }
         }

         //Sorting recursively
         if (low < high)
         quickSort(array, low, high);

         if (high > low)
              quickSort(array, low, high);
    }

     public static void printArray(int[] array) 
     {
         for (int input : array)
              System.out.print(input + " ");
      System.out.println();
     }
}

Answer 1

import java.io.*;
import java.util.*;
public class QuickSort
{
 public static void swap(int[] arr,int a,int b)
 {
    int temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;    

 }
 void quicksortfunc(int[] arr,int left,int right)
 {
    // System.out.println("Calling:"+Arrays.toString(arr));
     int size=right-left+1;
     if(size<=3)
         manualsort(arr,left,right);
     else
     {
     int pivot=medianof3(arr,left,right);
     System.out.println("Pivot is:"+pivot);
  //System.out.println(Arrays.toString(arr));
     int p_index=partitionfunc(arr,left,right,pivot);
     System.out.println("The p_index is:"+p_index);
     quicksortfunc(arr,left,p_index-1);
     quicksortfunc(arr,p_index+1,right);
     }
 }
 public static int medianof3(int[] arr,int left,int right)
 {
  int mid=(left+right)/2;
  if(arr[mid]<arr[left])
   swap(arr,mid,left);
  if(arr[right]<arr[left])
  swap(arr,right,left);
  if(arr[mid]>arr[right])
  swap(arr,mid,right);
  swap(arr,mid,right-1);
  return arr[right-1];
 }
 int partitionfunc(int[] arr, int left,int right,int pivot)
 {
     int i=left+1;
     int j=right-2;
     while(i<j)
     {
     while(arr[i]<pivot)
         i++;
     while(arr[j]>pivot)
         j--;
     if(i<j)
         swap(arr,i,j);
     }
     swap(arr,i,right-1);
             return i;
 }
 public static void manualsort(int[] arr,int left,int right)
 {
     int size=right-left+1;
     if(size<=1)
         return;
     if(size==2)
     {
         if(arr[right]<arr[left])
             swap(arr,left,right);
             return;
     }
     else
     {
     if(arr[right-1]<arr[left])
         swap(arr,right-1,left);
     if(arr[right]<arr[left])
         swap(arr,right,left);
     if(arr[right-1]>arr[right])
         swap(arr,right-1,right);
     }
 }
 public static void main(String[] args)
 {
  int[] arr={1,3,5,7,9,11,2,2,4,6,8,10,12,12};
  QuickSort obj=new QuickSort();
  obj.quicksortfunc(arr,0,13);
  System.out.println("The sorted array is:"+Arrays.toString(arr));
 }
}

Answer 2

First thing I would like to add is a shuffle operation before the first call in quicksort. Other than that if you want to take the median of first three elements that would be fine in the case you first shuffle the elements (in other case - especially if the array is sorted you would get not so good performance on quicksort).

Below is part of the code which is modified:

public static void sort(int[] array) {
    // Use collections shuffle 
    // (by converting to a List(extra memory) or any other shuffle method)
    shuffle(array);
    quickSort(array, 0, array.length - 1);
}

public static void quickSort(int[] array, int low, int high) {

   if (low >= high)
   return;

   // Selecting the  pivot
   int first = low;
   int second = low < high ? low + 1 : high;
   int third = low + 1 < high ? low + 2 : high;
   // median for first three
   int pivot = Math.max(Math.min(array[first],array[second]), 
                     Math.min(Math.max(array[first],array[second]),array[third]));

   while (low <= high) 
   {
        while (array[low] < pivot)
        {
             low++;
        }

        while (array[high] > pivot) 
        {
             high--;
        }

        if (low <= high)
        {
             int temp = array[low];
             array[low] = array[high];
             array[high] = temp;
             low++;
             high--;
         }
     }

     //Sorting recursively
     if (low < high)
     quickSort(array, low, high);

     if (high > low)
          quickSort(array, low, high);
}