private static int getPartition(int[] arr, int start, int end)
    {
        int partition = arr[start];
        int low = -1;
        int high = end + 1;
        
        while (low < high)
        {
            low++;
            while (arr[low] < partition && low < end) low++;
            
            high--;
            while (arr[high] > partition && high > start) high--;
            
            if (low < high)
            {
                int temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            }
        }
        
        return high;
    }