C++ quick sort

1/ Design an O(N) function called Move_Pivot_Copies (maybe list a prototype) that takes a partitioned vector and a pivot element, and copies any and all values that are equal to the pivot value to consecutive positions before the pivot position (you should leave the pivot position unchanged).

The function should return the start of the copies of the pivot element. For example, if your partitioned vector was

5

1

5

4

2

5

5

8

7

6

And the pivot location was 6, your function should rearrange the vector to look like ..and the function should return 3

1

4

2

5

5

5

5

8

7

6

(The elements before the 5s can be in any order).

2/ If we write the function we wrote in the previous question, we can now consider an optimized Quicksort, that looks like this:

void QuickSort(vector& v, int low, int high){

if(low < high){

int pivot = Partition(v, low, high);

int copy_start = Move_Pivot_Copies(v, low, high, pivot);

Quicksort (v, low, copy_start-1);

Quicksort (v, pivot+1, high);

}

1. Is this sort correct? (Does it correctly sort the vector?) Why or why not?
2. Is the Big-O performance of this function different from the normal Quicksorts? Why or why not?