1. Working with ChainSort.java apply incrementalInsertionSort algorithm to work with a linked chain instead of an array and implement a Shell sort for a linked chain. The skeleton of the application is provided.
   1. Before calling incrementalInsertionSort method, set the previous pointers to create the appropriate sub-chains as shown in the picture below:

2. During the sorting process, replace appropriate data without changing the next pointers.

public class ChainSort> { private Node firstNode; // reference to first node public ChainSort() { this.firstNode = null; } public void display() { Node currentNode = this.firstNode; while (currentNode != null) { System.out.print(currentNode.data + " "); currentNode = currentNode.next; } System.out.println(); } // end display public boolean isEmpty() { return this.firstNode == null; } // end isEmpty public void addToBeginning(T newEntry) { Node newNode = new Node<>(newEntry); newNode.next = this.firstNode; this.firstNode = newNode; } // end addToBeginning public void shellSort(int chainSize) { //TODO Project3   // for each space // create sub-chains: // set previousNode to the first node in the chain // set currentNode to the first node in the chain // with a for loop traverse nodes space times using currentNode // to find the second node of the first sub-chain // // with a while loop set up backward links for all sub-chains: // set currentNode's previous pointer to the previousNode // set previousNode to its next node and do the same with the currentNode // // call incrementalInsertionSort } // end shellSort /**  * Task: Sorts equally spaced elements of a linked chain into  * ascending order. Sub-chains created with a use of previous.  *  * @param space the space between the nodes of the  * elements to sort  */  private void incrementalInsertionSort( int space) { //TODO Project3   // when sorting do not change pointers - simply swap the data if needed } // end incrementalInsertionSort