Although [option A] is correct answer, but sometimes the wording in the question creates problem.
Lines from the Question:
"it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part."
If the underlined words means that the pivot belongs to left part, then the number of elements in the left part includes the pivot and therefore there is an infinite recursion for a particular instance.
Particular Instance: a = {5, 1, 2, 3, 4, 6, 7, 8, 9, 10}, n = 10, k = 5
Call 1:
Before partition : a = {5, 1, 2, 3, 4, 6, 7, 8, 9, 10}, n = 10, k = 5
partition(a, 10); pivot = a[0] = 5
After partition : a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
LeftPart = {1, 2, 3, 4, 5} <-- pivot 5 belongs to LeftPart
left_end = 5 = number of elements in LeftPart
Call 2: (left_end+1 > k) = (5+1 > 5) = true
Before partition : a = {1, 2, 3, 4, 5}, n = 5, k = 5
partition(a, 5); pivot = a[0] = 1
After partition : a = {1, 2, 3, 4, 5}
LeftPart = {1} <-- pivot 1 belongs to LeftPart
left_end = 1 = number of elements in LeftPart
Call 3: (left_end+1 > k) = (1+1 > 5) = false
Before partition : a = {3, 4, 5}, n = 3, k = 3
partition(a, 3); pivot = a[0] = 3
After partition : a = {3, 4, 5}
LeftPart = {3} <-- pivot 3 belongs to LeftPart
left_end = 1 = number of elements in LeftPart
Call 4: (left_end+1 > k) = (1+1 > 3) = false
Before partition : a = {5}, n = 1, k = 1
partition(a, 1); pivot = a[0] = 5
After partition : a = {5}
LeftPart = {5} <-- pivot 5 belongs to LeftPart
left_end = 1 = number of elements in LeftPart
Call 5: (left_end+1 > k) = (1+1 > 1) = true
Before partition : a = {5}, n = 1, k = 1
partition(a, 1); pivot = a[0] = 5
After partition : a = {5}
LeftPart = {5} <-- pivot 5 belongs to LeftPart
left_end = 1 = number of elements in LeftPart
Call 6: (left_end+1 > k) = (1+1 > 1) = true
Before partition : a = {5}, n = 1, k = 1
partition(a, 1); pivot = a[0] = 5
After partition : a = {5}
LeftPart = {5} <-- pivot 5 belongs to LeftPart
left_end = 1 = number of elements in LeftPart
....
Call 5 is same as Call 6, and this goes into infinite recursion.
....