Find the ith smallest element of the array in O(n)

How to find the ith smallest element of the array in O(n) time is a frequently asked question. The straightforward solution is sorting the array and return the ith element. However, for general cases, it's proven that sorting algorithms like merge sorting, is lower bound to O(nlogn). Thus finding the ith smallest element is unfeasible by a merge sorting. Although for some special cases, such as, the possible values or data range of the array is relatively small, counting sorting can give a O(n) solution, it doesn't work for general cases. The solution below works generally and the expected running time is O(n).

int find_ith_smallest_elem(int* A, int left, int right, int i) {
    if (left==right)  //only one element left, then it's the answer
        return A[left];
    pivot = random_partition(A,left,right);
    left_partition_length = pivot - left + 1; //1 counts for the pivot itself
    if (i==left_partition_length)
        return A[pivot];  //pivot is the answer
    else if (i<left_partition_length)
        return find_ith_smallest_elem(A,left,pivot-1,i);
    else
        return find_ith_smallest_elem(A,pivot+1,right,i-left_partition_length);
}

//randomly choose a pivot and partition the array into two parts, where the left part only
//contains elements smaller than the pivot while the right part only contains larger ones
int random_partition(int* A, int left, int right) {
    int pivot = rand(left,right);
    swap(A,pivot,right); // swap the pivot and the right-most element
    int pivot_value = A[right];
    int i = left - 1;
    for(int j=left; j<right; ++j) {
        if (A[j]<=pivot_value) {
            i++;
            swap(A,i,j); 
        }
    }
    swap(A,i+1,right);
    return i+1;
}