Recursive partition sort is inefficient

I have written a recursive method for a partition sort that sorts the array. However, when I use an array of more than 10-20 elements the program takes a really long time to complete. (On my computer a bubble sort of a 100,000 int array will take about 15-20 seconds, but with an array of only 30 ints my partition sort is taking around 45 seconds to be sorted.)

public static int[] partitionSortRecursive(int[] array, int beginning, int end)
{
    if (end < beginning)
        return array;

    int pivot = (array[beginning] + array[end]) / 2;
    int firstUnknown = beginning;
    int lastS1 = beginning - 1;
    int firstS3 = end + 1;

    while (firstUnknown < firstS3)
    {
        if (array[firstUnknown] == pivot)
        {
            firstUnknown++;
        }
        else if (array[firstUnknown] > pivot)
        {
            firstS3--;
            int temp = array[firstUnknown];
            array[firstUnknown] = array[firstS3];
            array[firstS3] = temp;
        }   
        else
        {
            lastS1++;
            int temp = array[firstUnknown];
            array[firstUnknown] = array[lastS1];
            array[lastS1] = temp;
            firstUnknown++;
        }

    }

    partitionSortRecursive(array, 0, lastS1);
    partitionSortRecursive(array, firstS3, end);

    return array;
}