[CC150][3.6] Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

stackSort.java

// if stack.size() is not allowed, use insertion sort, but it's an O(n^2) (time) algorithm, space : O(n)
// else, we can use MergeSort. Each merge operation has to put the biggest element into bottom of new stack
// so an extra reverse operation is needed. Time complexity is O(nlogn), space : O(nlgn)
import java.util.Stack;
import java.util.Random;

public class stackSort {
	public static<T extends Comparable<? super T>> Stack<T> insertSort(Stack<T> stack) {
		Stack<T> sorted = new Stack<T>();
		T temp;
		while (!stack.isEmpty()) {
			temp = stack.pop();
			while (!sorted.isEmpty() && temp.compareTo(sorted.peek()) < 0)
				stack.push(sorted.pop());
			sorted.push(temp);
		}
		return sorted;
	}
	
	public static<T extends Comparable<? super T>> Stack<T> mergeSort(Stack<T> stack) {
		return sort(stack);	
 	}
	
	private static<T extends Comparable<? super T>> Stack<T> sort(Stack<T> stack) {
		if (stack.size() <= 1) return stack;
		int mid = stack.size()/2;
		Stack<T> low = new Stack<T>();
		for (int i = 0; i < mid; i++)
			low.push(stack.pop());
		Stack<T> sortedLow = sort(low);
		Stack<T> sortedHigh = sort(stack);
		return merge(sortedLow, sortedHigh);
	}
	
	private static<T extends Comparable<? super T>> Stack<T> merge(Stack<T> a, Stack<T> b) {
		Stack<T> result = new Stack<T>();
		while (!a.isEmpty() && !b.isEmpty()) {
			if (a.peek().compareTo(b.peek()) >= 0)
				result.add(a.pop()); // always put bigger/equal one on bottom
			else result.add(b.pop());
		}
		while (!a.isEmpty())
			result.add(a.pop());
		while (!b.isEmpty())
			result.add(b.pop());
		return reverse(result); // after merger, the order should be reversed
	}
	
	private static<T extends Comparable<? super T>> Stack<T> reverse(Stack<T> a) {
		Stack<T> reverse = new Stack<T>();
		while (!a.isEmpty())
			reverse.push(a.pop());
		return reverse;
	}
	
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Stack<Integer> test1 = new Stack<Integer>();
		Stack<Integer> test2 = new Stack<Integer>();
		Random rd = new Random();
		int input;
		/********************test 1*********************/
		for (int i = 0; i < 20; i++) {
			input = rd.nextInt(500);
			test1.push(input);
			test2.push(input);
		}
		System.out.println("original stack: " +  test1.toString());
		test1 = stackSort.mergeSort(test1);
		test2 = stackSort.insertSort(test2);
		System.out.println("correctnenss test - MergeSort: " +  test1.toString());
		System.out.println("correctnenss test - InsertionSort: " +  test2.toString());
		
		
		/********************test 2*********************/
		System.out.println("10000 random elements");
		test1.clear();
		test2.clear();
		for (int i = 0; i < 10000; i++) {
			input = rd.nextInt(50000);
			test1.push(input);
			test2.push(input);
		}

		long start = System.currentTimeMillis();
		test1 = stackSort.mergeSort(test1);
		long end = System.currentTimeMillis();
		System.out.println("Merge-sort : " + (end-start) + " ms");
		
		start = System.currentTimeMillis();
		test2 = stackSort.insertSort(test2);
		end = System.currentTimeMillis();
		System.out.println("Insertion-sort : " + (end-start) + " ms");
	}
}

/* Test result
original stack: [93, 149, 448, 331, 352, 489, 87, 384, 159, 375, 358, 173, 303, 267, 293, 178, 12, 43, 414, 266]
correctnenss test - MergeSort: [12, 43, 87, 93, 149, 159, 173, 178, 266, 267, 293, 303, 331, 352, 358, 375, 384, 414, 448, 489]
correctnenss test - InsertionSort: [12, 43, 87, 93, 149, 159, 173, 178, 266, 267, 293, 303, 331, 352, 358, 375, 384, 414, 448, 489]
Test 2 : 10000 random elements
Merge-sort : 141 ms
Insertion-sort : 7432 ms
*/