Algorithm – Quicksort: iteration or recursive

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 stack = new Stack();
 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  if (arr[ l]  l++;
} else if (arr[h] >= piv) {
 h--;
} else {
 swap( arr,l,h);
 }
 }
 int idx = h;
 if (arr[h]  sw ap(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  for (int i = 0; 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(tempA rr,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);
} 

I learned quick sort and how to implement it in recursive and iterative methods.
In iterative methods:

> (0… n) Push into the stack
>Use a pivot table to partition the given array
>Pop the top element.
>If the range contains multiple elements, push the partition (index range) into The stack
>performs the above 3 steps until the stack is empty

The recursive version is the normal version defined in the wiki.

I learned that the recursive algorithm is always slower than the iterative algorithm .
So, in terms of time complexity, which method is more popular (memory is not an issue)?
Which one is used fast enough in programming competitions?
c Does STL sort() use a recursive method?

In terms of (asymptotic) time complexity – they are all the same.

"Recursion is slower than iteration "– The rationale behind this statement is due to the overhead of the recursive stack (saving and restoring the environment between calls).
However, these are constants for ops, not changing the number of "iterations".

Recursion and iterative quick sort are both O(nlogn) average case and O(n^2) worst case.

Edit:

Just for the fun of it I ran the add-on Go to the benchmark test of the (java) code of the post, and then I run the wilcoxon statistic test to check the probability that the running time is indeed different

The result is decisive (P_VALUE = 2.6e-34, which means The probability that they are the same is 2.6 * 10 ^ -34-very unlikely). But the answer is not what you expected.
The average of the iterative solution is 408.86 ms, and the recursive average is 236.81 ms

So-your assumption is incorrect, the recursive solution is faster (for my machine and java at least) and then the iterative 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 stack = new Stack(); 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  if (arr[l]  l++;
} else if (arr [h] >= piv) {
 h--;
} else {
 swap(arr,l,h);
 }
 }
 int idx = h;
 if (arr[h]  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  for (int i = 0; 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)(Sy stem.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);
}