Proof of QuickSort algorithm correctness

Question

Recently I’ve studied QuickSort and understood its general idea.

Basically, we do the following:

1. Pick an element from the array (no matter which one and how in this context)
2. Rearrange elements in the array so that elements less than the pivot are placed prior to it (in the left part of the array), and ones that are greater than the pivot are placed after it (in the right part).
3. Apply these procedures to the left and right parts of the array.

Everything looks quite clear, but my question is: why does it eventually sorts the entire array?

I’ve read lots of articles about the QuickSort, but none of them provides a clear proof that algorithm does really work in a way they describe. So I’m looking for such a proof.

I realize that:

• Array of one element (i.e with length 1) is already sorted.
• After any partition the pivot is placed on it’s final position.

So what’s the proof of the fact that after applying QuickSort procedure to a given array of length N its elements will be ordered after a procedure completes?

P.S. I’ve seen several proofs based on mathematical induction. Unfortunately, I’m not familiar with it yet, so I’m primarily looking for non-induction proof.

Here they are:

• https://www.cs.mcgill.ca/~dprecup/courses/IntroCS/Lectures/comp250-lecture17.pdf
• Trying to understand this Quicksort Correctness proof
• https://course.ccs.neu.edu/cs5010sp17/Efficiency/quicksort5.html