It's not such an arcane algorithm. Choose a pivot element, (say) p. Rearrange the array into left_sub_array + [p] + right_sub_array such that all elements of le

It's not such an arcane algorithm. Choose a pivot element, (say) p. Rearrange the array into left_sub_array + [p] + right_sub_array such that all elements of left_sub_array are no greater than p, and all elements of right_sub_array are greater than p. Then recursively sort the left and right sub-arrays. If you don't remember this, it's OK. If I was the interviewer I'd still give you the description above and see if you could implement it. Most candidates cannot.