3 way quick sort | Dijkstra 3-way partitioning | Improvement with duplicate keys

 
class ThreeWayQuickSort {
    public static void sort(int[] array) {
        sort(array, 0, array.length-1);
    }
    
    private static void sort(int[] array, int low, int high) {
        if(high <= low) { 
            return;
        }
        // 3-way partition
        int v = array[low];
        int lt = low;
        int gt = high;
        int i = low;
        while(i <= gt) {
            if(array[i] < v) {
                swap(array, i++, lt++);
            } else if (array[i] > v) {
                swap(array, i, gt--);
            } else {
                i++;
            }
        }
        
        sort(array, low, lt-1);
        sort(array, gt+1, high);
    }
    
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    private static void display(int[] array) {
        for(int key : array) {
            System.out.print(key + " ");
        }
    }
    
	public static void main (String[] args) {
	    // Test average case 
		int[] array = new int[] {11,13,7,12,7,7,7,7,7,16,9,24,5,5,5,5,5,7,7,7,10,3};
		System.out.println("Unsorted array : ");
		display(array);
		
		sort(array);
		System.out.println("\nSorted array : ");
		display(array);
	}
}

 
Unsorted array : 
11 13 7 12 7 7 7 7 7 16 9 24 5 5 5 5 5 7 7 7 10 3 
Sorted array : 
3 5 5 5 5 5 7 7 7 7 7 7 7 7 7 9 10 11 12 13 16 24