Given an Unsorted Array , I want to find out median of array without sorting an array or partially sorting an array with minimum possible complexity using Opencl .Should I use Parallel bubble sort and partially sort the array to get median or any other method.Plz suggest me as early as possible.

array is of around 500000 elements....