Q3_6.java

import java.util.Stack;
 
public class Q3_6{
	public static void main(String[] args){
		
		Stack<Integer> test = new Stack<Integer>();
		test.push(5);
		test.push(2);
		test.push(3);
		test.push(1);
		test.push(4);
		test.push(6);
		Stack<Integer> result  = sortByMerge(test, 6);
		assert isSorted(result);	
	}
	
	static boolean isSorted(Stack<Integer>  stack){
		if(stack.size()==0)
			return true;
		
		while(stack.size()>1){
			int x = stack.pop();
			if(x<stack.peek())
				return false;
		}
		return true;
	}
	
	static void sort(Stack<Integer> s){
		Stack<Integer> buffer = new Stack<Integer>();
		while(!s.isEmpty()){
			int temp = s.pop();
			while(!buffer.isEmpty() && temp > buffer.peek()){
				s.push(buffer.pop());
			}
			buffer.push(temp);
		}
		while(!buffer.isEmpty()){
			s.push(buffer.pop());
		}
	}
	static Stack<Integer> sortByMerge(Stack<Integer> s, int size){
		if(size <= 1){			
			return s;			
		}
			
		Stack<Integer> buffer = new Stack<Integer>();
		int half = size/2;
		for(int i = half; i >0; i--){
			buffer.push(s.pop());
		} 
		
		Stack<Integer> sortedS = sortByMerge(s,size-half);
		Stack<Integer> sortedBuffer = sortByMerge(buffer, half);		
		return merge(sortedS,sortedBuffer);
		
	}
	
	static Stack<Integer> merge(Stack<Integer> s1,Stack<Integer> s2){
		Stack<Integer> buffer = new Stack<Integer>();
		while(!s1.isEmpty() && !s2.isEmpty()){
			if(s1.peek()>s2.peek())
				buffer.push(s1.pop());
			else buffer.push(s2.pop());
		}
		if(!s1.isEmpty()){
			while(!s1.isEmpty())
				buffer.push(s1.pop());
		}
		if(!s2.isEmpty()){
			while(!s2.isEmpty())
				buffer.push(s2.pop());
		}
		
		while(!buffer.isEmpty()){
			s1.push(buffer.pop());
		}
		return s1;
		
	}
	
	
	
	
}