Quicksort returns an unsorted array

Question

I have two days trying to understand why my quicksort function returns all but two items, sorted in the correct order.

When entering

quicksort([0,7,3,11,23,87,999,1023,12,713,5,6,9])

Outputs

[0, 6, 3, 5, 7, 9, 11, 12, 23, 87, 713, 999, 1023]

What do you think is wrong with the function?

def quicksort(array):
    #Base case
    if len(array) <= 1:
        return array
    #Choose pivot always at the left part and partition array around it
    Pivot = partition(array,0,len(array));
    #Add values for left and righ arrays
    left = array[:Pivot]
    right = array[Pivot+1:]
    #Add recursive calls
    left = quicksort(left)
    right = quicksort(right)
    #Append Pivot at the end of left array
    left.append(array[Pivot])
    return left+right

For completion questions, I add a section function, but I'm pretty sure that the problem does not exist.

def partition(array,left,right):
    #If pivot is not on leftmost, swap to make it leftmost
    Pivot = array[left]
    i = left+1
    for j in range(left+1,right):
        if array[j] < Pivot:
            #Swap array[j] and array[i]
            array[j], array[i] = array[i], array[j]
            i += 1;
    #Swap pivot and A[i-1]        
    array[left], array[i-1] = array[i-1], array[left]
    return left

Answer 1

Your split function always returns an argument leftsince it was supplied without changing it. I think you intend to return the final position of the rotation element.

Answer 2

Just to complete, using pythons understanding lists, the code is much easier to implement and read.

def qs(l):
    if len(l) < 2:
        return l
    pivot = l.pop()
    left = [x for x in l if x < pivot]
    right = [x for x in l if x >= pivot]
    return qs(left) + [pivot] + qs(right)

, .

• 1 0
• .
• , , , , pivot
• quicksort