LOGIC:

1. Get a passed linked list -> 9, 3, 4, 12, 2, 5

2. Using the value of the head (9) of the passed linked list, create a new node , called CreatedHead

3. create a pointer node called runner which points to 2nd node of the passed linked list (3)

while (runner != null)

FIRST LOOP

Create a pointer node called arrow which points to the createdhead (9)

Create a pointer node called getNextNode which gets the 3rd node's address (4)

As 3 <= 9 (runner.value <= createdHead.value)

create a list by changing places:

     3:9:null  (exchange 1st and 2nd node)

getNextNode gets the 4th node's address (12)

runner = 4= getNextNode

2nd LOOP

(Bring the 3rd Node (4) and see)

Arrow = 3 = createdHead , getNextNode = 12 = runner.address;

As ( 4 > 3 ) runner.value > createdHead.value go to else

ELSE:::

2nd WHILE ::::::

                As runner.value > Arrow.value ( 4>3) and && (4 < 9) runner.value <= Arrow.address.value

                3:4:9:null  (exchange 2nd and 3rd node)

Keep incrementing Arrow till null is encountered at 9

IF: skip If as runner.value (4) < Arrow.value (9)

runner = 12

3rd LOOP

(Bring the 4th Node 12 and see)

Arrow = 3 = createdHead , getNextNode = 2 = runner.address;

As ( 12 > 3 ) runner.value > createdHead.value

ELSE:::

2nd WHILE ::::::

                As runner.value > Arrow.value ( 12>3) and && (12 > 4) runner.value > Arrow.address.value

                Keep incrementing Arrow till null is encountered at 9 ( check all elements of the new list against 4th element to see if they are less than the 4th element (12).

        - As 12 > 9 , so 12 is made the last elemnt of the new list having address of null , and 9's address points to it

3:4:9:12: null

4th LOOP

(Bring the 5th Node 2 and see)

Runner = 2

Arrow = 3 = createdHead , getNextNode = 5 = runner.address;

As 2 <= 3 (runner.value <= createdHead.value)

 exchange 1st and 5th node

2:3:4:9:12:null

5th LOOP

Runner = 5

Arrow = 2 = createdHead , getNextNode = null = runner.address;

runner.value (5) > createdHead.value (2)

ELSE:::

2nd WHILE ::::::

                10. As runner.value > Arrow.value ( 5 > 2 ) and && (5 > 3 ) runner.value > Arrow.address.value

                12. Keep incrementing Arrow (move through the newly created list ) till

runner.value > Arrow.value ( 5 > 4 ) and && (5 <= 9 ) runner.value <= Arrow.address.value

- put 5 between 4 and 9

2:3:4:5:9:12:null

 ///////////////////////The Code///////////////////////////////////////////////////////////////////////////



class Node {
int value;
Node address;
Node(int X, Node Y) {
  value = X;
  address = Y;
}
}
 
public class Arrays {
    public static Node sortInsertion(Node passedhead) {
 //9, 3, 4, 12, 2, 5 - passed linked list . passed head == 9
        if (passedhead == null || passedhead.address == null)
            return passedhead;
 //Create a new Node , having the passed head's value == 9, address as null
        Node createdHead = new Node(passedhead.value , null);
        //the runner Node points to second node, having value == 3
        Node runner = passedhead.address;
 
        while (runner != null) {
            //In first while loop, Node Arrow points to createdHead 
                  
            Node Arrow = createdHead;
             Node getNextNode = runner.address;
                           
            if (runner.value <= createdHead.value)
            {
                //create a temporary node to store createdHead's address
                //temp Node's value=9
                Node temp = createdHead;
                //createdHead.value=3
                createdHead = runner;
                //createdHead.address=Node having value 9
                createdHead.address = temp;
            }
           
          
            else
            {
               
                while (Arrow.address != null)
                {
                   
                    if (runner.value > Arrow.value && runner.value <= Arrow.address.value)
                    {
                      
                        Node temp = Arrow.address;
                        Arrow.address = runner;
                        runner.address = temp;
                    }
                   
                    Arrow = Arrow.address;
                }
 
                if (Arrow.address == null && runner.value > Arrow.value)
                {
                    Arrow.address = runner;
                    runner.address = null;
                }
            }
 
           
            printL(createdHead);
            runner = getNextNode;
        }
 
        return createdHead;
    }
 
    public static void main(String[] args) {
        Node n1 = new Node(9,null);
        Node n2 = new Node(3,null);
        Node n3 = new Node(4,null);
 
        Node n4 = new Node(12,null);
        Node n5 = new Node(2,null);
        Node n6 = new Node(5,null);
 
        n1.address = n2;
        n2.address = n3;
        n3.address = n4;
        n4.address = n5;
        n5.address = n6;
        n1 = sortInsertion(n1);
        System.out.println("9, 3, 4, 12, 2, 5 - passed linked list ");
        printL(n1);
 
    }
 
    public static void printL(Node head) {
        if(head != null){
            System.out.print(head.value + " ");
            while (head.address != null) {
                System.out.print(head.address.value + " ");
                head = head.address;
            }
            System.out.println();
        }
 
    }
}