Quicksort: Iterative or Recursive

Question

I learnt about quick sort and how it can be implemented in both Recursive and Iterative method.
In Iterative method:

1. Push the range (0...n) into the stack
2. Partition the given array with a pivot
3. Pop the top element.
4. Push the partitions (index range) onto a stack if the range has more than one element
5. Do the above 3 steps, till the stack is empty

And the recursive version is the normal one defined in wiki.

I learnt that recursive algorithms are always slower than their iterative counterpart.
So, Which method is preferred in terms of time complexity (memory is not a concern)?
Which one is fast enough to use in Programming contest?
Is c++ STL sort() using a recursive approach?

Answer 1

In terms of (asymptotic) time complexity - they are both the same.

"Recursive is slower then iterative" - the rational behind this statement is because of the overhead of the recursive stack (saving and restoring the environment between calls).
However -these are constant number of ops, while not changing the number of "iterations".

Both recursive and iterative quicksort are O(nlogn) average case and O(n^2) worst case.

---

EDIT:

just for the fun of it I ran a benchmark with the (java) code attached to the post , and then I ran wilcoxon statistic test, to check what is the probability that the running times are indeed distinct

The results may be conclusive (P_VALUE=2.6e-34, https://en.wikipedia.org/wiki/P-value. Remember that the P_VALUE is P(T >= t | H) where T is the test statistic and H is the null hypothesis). But the answer is not what you expected.
The average of the iterative solution was 408.86 ms while of recursive was 236.81 ms

(Note - I used Integer and not int as argument to recursiveQsort() - otherwise the recursive would have achieved much better, because it doesn't have to box a lot of integers, which is also time consuming - I did it because the iterative solution has no choice but doing so.

Thus - your assumption is not true, the recursive solution is faster (for my machine and java for the very least) than the iterative one with P_VALUE=2.6e-34.

public static void recursiveQsort(int[] arr,Integer start, Integer end) {      if (end - start < 2) return; //stop clause     int p = start + ((end-start)/2);     p = partition(arr,p,start,end);     recursiveQsort(arr, start, p);     recursiveQsort(arr, p+1, end);  }  public static void iterativeQsort(int[] arr) {      Stack<Integer> stack = new Stack<Integer>();     stack.push(0);     stack.push(arr.length);     while (!stack.isEmpty()) {         int end = stack.pop();         int start = stack.pop();         if (end - start < 2) continue;         int p = start + ((end-start)/2);         p = partition(arr,p,start,end);          stack.push(p+1);         stack.push(end);          stack.push(start);         stack.push(p);      } }  private static int partition(int[] arr, int p, int start, int end) {     int l = start;     int h = end - 2;     int piv = arr[p];     swap(arr,p,end-1);      while (l < h) {         if (arr[l] < piv) {             l++;         } else if (arr[h] >= piv) {              h--;         } else {              swap(arr,l,h);         }     }     int idx = h;     if (arr[h] < piv) idx++;     swap(arr,end-1,idx);     return idx; } private static void swap(int[] arr, int i, int j) {      int temp = arr[i];     arr[i] = arr[j];     arr[j] = temp; }  public static void main(String... args) throws Exception {     Random r = new Random(1);     int SIZE = 1000000;     int N = 100;     int[] arr = new int[SIZE];     int[] millisRecursive = new int[N];     int[] millisIterative = new int[N];     for (int t = 0; t < N; t++) {          for (int i = 0; i < SIZE; i++) {              arr[i] = r.nextInt(SIZE);         }         int[] tempArr = Arrays.copyOf(arr, arr.length);                  long start = System.currentTimeMillis();         iterativeQsort(tempArr);         millisIterative[t] = (int)(System.currentTimeMillis()-start);                  tempArr = Arrays.copyOf(arr, arr.length);                  start = System.currentTimeMillis();         recursvieQsort(tempArr,0,arr.length);         millisRecursive[t] = (int)(System.currentTimeMillis()-start);     }     int sum = 0;     for (int x : millisRecursive) {         System.out.println(x);         sum += x;     }     System.out.println("end of recursive. AVG = " + ((double)sum)/millisRecursive.length);     sum = 0;     for (int x : millisIterative) {         System.out.println(x);         sum += x;     }     System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length); }