Threeway Quicksort is a sorting algorithm that works as follows. 

Given a sequence S of n numbers, take S[0], the first number in S, let us call it pivot. Go through the remaining numbers in S in the following way. Start with i = 1 and j = n-1. Compare S[i] and S[j] with pivot. If S[i] is less than or equal to pivot, then set i = i+1. If S[j] is greater than or equal to pivot, set j = j-1. Continue this way until S[i] is greater than pivot and S[j] is less than pivot for some 1 <= i < j <= n-1. Swap S[i] with S[j].

Now S[i] becomes less than equal to pivot and S[j] greater than equal to pivot. Continue as before. At some point j = i+1 and S[i] is less than or equal to pivot and S[j] is greater than or equal to pivot. Swap S[i] with pivot. Now numbers S[0] thru S[i-1] are less than or equal to S[i] and numbers S[i+1] thru S[n-1] are greater than or equal to S[i]. Hence S[i] is in its correct location. If i is between n/2 and 2n/3, then recursively sort S[0] thru S[i-1] and S[i+1] thru S[n-1]. If i > 2n/3, then do splitting done via pivot as above for subsequence S[0] thru S[i-1]. This divides the sequence in three parts. Recursively sort each part. Similarly, if i < n/3, split the subsequence S[i+1] thru S[n-1] and then recursively sort the three parts.

Write a program implementing Randomized Quicksort.