This question is misleading and poorly specified. In quicksort the partition method does not get called recursively and the sorting is done in-place. What is described here is a version of merge sort, taking additional O(n) storage space. There's no way to pass this question with actual quicksort, because the order of the items in the sub-arrays does not get preserved.

Read a bit on quicksort on Wikipedia.

Additionally, the fact that the first item is selected as the pivot should be specified in the question, not expected to be inferred from the example.

Another well thought out challenge. I must say that QuickSort is rather a difficult topic. However, the explanations, the expected output and the exercise before this made it look easy. Again, an easy solution could be achieved by first tackling the previous exercise and following the instructions in this exercise carefully. The diagram on the expected output guides the logic behind the recursion.

The sort method - takes in an array and returns an array

1. If the array length < 2, do nothing it's already sorted.
2. If the array length = 2; check if first element is greater than the second element and swap.
3. If the array length > 2, i. partition the array into two ii. call sort method passing the left array iii. call sort method passing the right array iv. merger the left array with the partition and the right array in this other. iv. print the resulting sub array before every return v. return the sub array.

I must say that this is the most clearer instruction of all the challenges I have tackled so far. Could it be because quick sort is rather a problematic exercise?

When the problem gives the function declaration already, I tend to stick with it and not change it. You can solve this problem with the given vector parameter. Notice arr is passed in as a reference, so there is no need to return back another vector. The exit case can just be detected if size < 2, don't need to swap when size == 2. I tested with a swap, but it just gave me the same answer. Hope this helps anyone stuck on this problem.

[C++]

void quickSort(vector &arr) {

// Complete this function

int size = arr.size();
if (size < 2) {
    return;
}

vector <int> leftArray;
vector <int> rightArray;

int pivot = arr[0];

for (int i = 1; i < size; ++i) {
    if (arr[i] <= pivot) {
        leftArray.push_back(arr[i]);
    }
    else {
        rightArray.push_back(arr[i]);
    }
}
quickSort(leftArray);
quickSort(rightArray);

int index = 0;

// Copy left array back into the original array
for (unsigned int l = 0; l < leftArray.size(); ++l) {
    arr[index++] = leftArray[l];
    cout << leftArray[l] << " ";
}

// Copy the pivot between left & right arrays
arr[index++] = pivot;
cout << pivot << " ";

// Copy right array back into the original array
for (unsigned int r = 0; r < rightArray.size(); ++r) {
    arr[index++] = rightArray[r];
    cout << rightArray[r] << " ";
}
cout << endl;

}

Is this the right way to solve this challenge in Python, or can someone improve it?

def quick_sort(*ar):
    p, *a = ar
    first, last = [], []
    for i in a:
        if i < p:
            first.append(i)
        else:
            last.append(i)
    if len(first) > 1:
        first = quick_sort(*first)
        print(*first)
    if len(last) > 1:
        last = quick_sort(*last)
        print(*last)
    return first + [p] + last

n = int(input())
p, *a = map(int, input().split())
print(*quick_sort(p, *a))

I used a different partition function than the one you guys are using i think my output for first test case is

1 2 1 2 3 8 9 7 8 9 1 2 3 5 7 8 9. Just like Quicksort1-Partition which checks for variations in partition shouldn't this do the same?