package test;

import java.util.*;

//Bottom Up MergeSort
public class BUMS
{
	//Preconditions: Takes a list of integers
	//Postconditions: list is now sorted in ascending order
	/**CODE DESCRIPTION
	Turns the list into a list of lists and then calls the sort method on that
	*/
	public static void sort(List<Integer> list)
	{
		List< List<Integer> > llist = new ArrayList< List<Integer> >();
		
		for(Integer x : list)
		{
			llist.add(new ArrayList<Integer>());
			llist.get(llist.size() - 1).add(x);
		}
		
		//sorts llist so now it only contains 1 sorted list of integers
		Sort(llist);

		//copies the elements over to list
		list.clear();
		list.addAll(llist.get(0));
	}

	//Preconditions: Takes an array of integers
	//Postconditions: array is now sorted in ascending order
	/**CODE DESCRIPTION
	Turns the array into a list of lists and then calls the sort method on that
	list is then copied into the array
	*/
	public static void sort(Integer[] array)
	{
		List< List<Integer> > llist = new ArrayList< List<Integer> >();
		
		for(Integer x : array)
		{
			llist.add(new ArrayList<Integer>());
			llist.get(llist.size() - 1).add(x);
		}
		
		//sorts llist so now it only contins 1 sorted list of integers
		Sort(llist);

		//copies the elements over to list
		for(int i = 0; i < array.length; i++)
			array[i] = llist.get(0).get(i);
	}

	//Preconditions:llist is a list of lists, each of which has 1 integer
	//Postconditions:llist will contain only one list, which is the sorted integers in ascending order
	private static void Sort(List< List<Integer> > llist)
	{
		while(llist.size() > 1)
			for(int i = 0; i < llist.size() - 1; i++)
				merge(llist, i);
	}

	//Preconditions:merges llist.get(index) with llist.get(index + 1);
	//the 2 lists must be in sorted order
	//Postconditions:the list llist.get(index) will the the sorted list of the combined lists in ascending order
	//WARNING: THE OTHER LIST WILL BE REMOVED FROM LLIST, DECREASING ITS SIZE AND CHANGING INDEXES
	private static void merge(List< List<Integer> > llist, int index) 
	{
		ListIterator<Integer> it1 = llist.get(index).listIterator();
		ListIterator<Integer> it2 = llist.get(index + 1).listIterator();

		while(it1.hasNext() && it2.hasNext())
		{
			if(it1.next() < it2.next())
				it2.previous();
			else 
			{
				it1.previous();
				it1.add(it2.previous());
				it2.remove();
			}		
		}
		if(it2.hasNext())
			llist.get(index).addAll(llist.get(index + 1));
		llist.remove(index + 1);
	}
}