• Time Complexity : O(N^2)
• Space Complexity : O(1)
• Let suppose we have 4 people having sorted amount of rupees.

• Now you have to join these people in line with sorting order.
• suppose you have 8k rupees, you have to fit in such a way as shown in figure.

Consider an array

Left side of the array is sorted checking the right side first term.

public class Main
{
	public static void main(String[] args) {
		int[] arr = new int[] {12,15,19,20,5};
		int j,key;                      //sorted     || unsort
		for(int i=1;i<arr.length;i++) // 12 15 19 20 || 5
		{
		    key = arr[i]; //key-5 i-4
		    j=i-1; //j-3 and arr[j] - 20
		    while(j>=0 && arr[j]>key) //20>5 j-3 ... 19>7 j-2...15>7 j-1...12>7 j-0...j=-1
		    {
		        arr[j+1] = arr[j];//1st iteration - 12 15 19 20* j-3
		        j--;              //2nd iteration - 12 15 19* 20 j-2
		    } //j=-1             //3rd iteration - 12 15* 19 20 j-1  
		                         //4th iteration - 12* 15 19 20 j-0
		                        //5th iteration - 12 15 19 20 j=-1
		    arr[j+1] = key;       
		}
		for(int i=0;i<arr.length;i++)
		{
		    System.out.println(arr[i]);
		}
	}
}