import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Naloga2 {
private static int m_cnt;
private static int m_in[];
public static int Sort(int in [],int cnt)
{
int m_in[]=new int[cnt];
m_cnt = cnt;
for(int i=0;i<m_cnt;i++)
{
m_in[i]=in[i];
}
return mSort(0, m_cnt);
}
public static int mSort(int ind, int cnt)
{
int tmp;
int left, right;
if (cnt == 1)
{
return 0;
}
left = (cnt + 1) / 2;
right = cnt / 2;
if (cnt == 2)
{
mDisplay(ind, 1, 1);
if (m_in[ind] > m_in[ind+1])
{
tmp = m_in[ind];
m_in[ind]= m_in[ind+1];
m_in[ind+1]= tmp;
}
mDisplay(ind, 2, 0);
} else {
mDisplay(ind, left, right);
mSort(ind, left); // left
mSort(ind+left, right); //right
mOrder(ind, left, right);
mDisplay(ind, left + right, 0);
}
return 0;
}
public static int mOrder(int ind, int left, int right)
{
int i, a, b;
int tmp []=new int [left+right];
a = b = 0;
for (i = 0; i < (left+right); ++i)
{
if ((m_in[ind+a] > m_in[ind+left+b] && b < right) || a >= left)
{
tmp[i] = m_in[ind+left+b];
++b;
}
else if (a < left)
{
tmp[i] = m_in[ind+a];
++a;
}
}
for(int x=0;x<(left+right);x++)
{
m_in[ind+x]=tmp[x];
}
return 0;
}
public static void mDisplay(int ind, int left, int right)
{
int i, j;
for (i = 0; i < left; ++i)
{
System.out.print(m_in[ind+i]+" ");
}
if (right == 0)
{
System.out.println();
return;
}
System.out.print("| ");
for (j = 0; j < right; ++j)
{
System.out.print(m_in[ind+i+j]+" ");
}
System.out.println();
}
public static ArrayList<Integer> input(ArrayList<Integer> list,Scanner sc) {
while(true)
{
if(sc.hasNextInt())
{
list.add(sc.nextInt());
}
else
{
break;
}
}
return (list);
}
public static int [] retTable(int [] table, ArrayList<Integer> list) {
for(int i=0;i<list.size();i++)
{
table[i]=(int)list.get(i);
}
return (table);
}
public static void main(String [] args) {
String algorithm=args[0];
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<Integer> listNew = new ArrayList<Integer>();
listNew=input(list,sc);
int [] table = new int[listNew.size()];
int [] tableNew = new int[listNew.size()];
tableNew=retTable(table,listNew);
if(algorithm.equals("QS"))
{
//izpisiSledQS(tabelaNova);
}
else if(algorithm.equals("MS"))
{
Sort(tableNew,tableNew.length);
}
else
{
System.out.println("Pass sorting algorithm as argument.");
}
}
}