/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	     String entry = "kisakye";
	     System.out.println("Before sorting: "+ entry);
	     String sorted = InsertionSort(entry);
	     System.out.println("Insertion sort: "+ sorted);
 
 
	}
 
	public static String InsertionSort(String word){
		char [] a = word.toCharArray(); // tranforms the string in to character array
		int n = a.length; //length of the character array
		for(int i=1; i<n; i++){ // checks for all the items in the array
			int j = i-1; //position of char below the char
			char cur = a[i];// current char
			while((j>=0) && (a[j]>cur))
				a[j+1] = a[j--]; // swap the chars
			a[j+1] = cur; //do not swap the chars
 
		}
 
		return new String(a);
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJICAgICBTdHJpbmcgZW50cnkgPSAia2lzYWt5ZSI7CgkgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiQmVmb3JlIHNvcnRpbmc6ICIrIGVudHJ5KTsKCSAgICAgU3RyaW5nIHNvcnRlZCA9IEluc2VydGlvblNvcnQoZW50cnkpOwoJICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIkluc2VydGlvbiBzb3J0OiAiKyBzb3J0ZWQpOwoJICAgICAKCSAgICAgCgl9CgkKCXB1YmxpYyBzdGF0aWMgU3RyaW5nIEluc2VydGlvblNvcnQoU3RyaW5nIHdvcmQpewoJCWNoYXIgW10gYSA9IHdvcmQudG9DaGFyQXJyYXkoKTsgLy8gdHJhbmZvcm1zIHRoZSBzdHJpbmcgaW4gdG8gY2hhcmFjdGVyIGFycmF5CgkJaW50IG4gPSBhLmxlbmd0aDsgLy9sZW5ndGggb2YgdGhlIGNoYXJhY3RlciBhcnJheQoJCWZvcihpbnQgaT0xOyBpPG47IGkrKyl7IC8vIGNoZWNrcyBmb3IgYWxsIHRoZSBpdGVtcyBpbiB0aGUgYXJyYXkKCQkJaW50IGogPSBpLTE7IC8vcG9zaXRpb24gb2YgY2hhciBiZWxvdyB0aGUgY2hhcgoJCQljaGFyIGN1ciA9IGFbaV07Ly8gY3VycmVudCBjaGFyCgkJCXdoaWxlKChqPj0wKSAmJiAoYVtqXT5jdXIpKQoJCQkJYVtqKzFdID0gYVtqLS1dOyAvLyBzd2FwIHRoZSBjaGFycwoJCQlhW2orMV0gPSBjdXI7IC8vZG8gbm90IHN3YXAgdGhlIGNoYXJzCgkJCQoJCX0KCQkKCQlyZXR1cm4gbmV3IFN0cmluZyhhKTsKCX0KfQ==