The Non-recursion Algorithmic of Merging Sort and QuickSort|快速排序和归并排序的非递归实现

public static int[] QuickSort(int[] arr, int left, int right) {

    Stack<Integer> stack = new Stack<>();

    if (left < right) {
	stack.push(left);
	stack.push(right);
	while (!stack.isEmpty()) {
		int height = stack.pop();
		int low = stack.pop();
		int index = partition(arr, low, height);
			if (index - 1 > low) {
				stack.push(low);
				stack.push(index - 1);
			}

			if (index + 1 < height) {
				stack.push(index + 1);
				stack.push(height);
			}
		}
	}
   return arr;
}

private static int partition(int[] list, int first, int last) {
	int pivot = list[first];
	int low = first + 1;
	int high = last;

	while (high > low) {

		while (low <= high && list[low] <= pivot)
			low++;

		while (low <= high && list[high] > pivot)
			high--;

		if (high > low) {
			int temp = list[high];
			list[high] = list[low];
			list[low] = temp;
		}
	}

	while (high > first && list[high] >= pivot)
		high--;

	if (pivot > list[high]) {
		list[first] = list[high];
		list[high] = pivot;
		return high;
	} else {
		return first;
	}
}

public static void mergeSort(int[] arr, int[] temp) {
		
    // 从 1开始分割，与递归不同的是，递归由数组长度一分为二最后到1，
    // 而非递归则是从1开始扩大二倍直到数组长度 
    int len = 1;
	    
    while (arr.length > len) {
	        
           // 完全二叉树一层内的遍历
	   for (int i = 0; i + len <= arr.length - 1; i += len * 2) {
	   int left = i;
	   int mid = i + len - 1;
	   int right = i + len * 2 - 1;
	            
	    // 防止超出数组长度
	    if (right > arr.length - 1)
	          right = arr.length - 1;
	            
	    // 合并排序相同
	   merge(arr, left, mid, right, temp);
	    }
	        
	  // 下一层
	  len *= 2;
    }
	
}
	
	
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		
	int i = left; 
	int j = mid + 1; 
	int t = 0; 
				
	while (i <= mid && j <= right) {
			
		if(arr[i] <= arr[j]) {
			temp[t] = arr[i];
			t += 1;
			i += 1;
		} else { 
			temp[t] = arr[j];
			t += 1;
			j += 1;
		}
	}
			
	while( i <= mid) { 
		temp[t] = arr[i];
		t += 1;
		i += 1;	
	}
		
	while( j <= right) { 
		temp[t] = arr[j];
		t += 1;
		j += 1;	
	}
		
			
	t = 0;
	int tempLeft = left; 
		
	while(tempLeft <= right) { 
		arr[tempLeft] = temp[t];
		t += 1;
		tempLeft += 1;
	}
		
}