## Given a linked list, sort the list using insertion sort. Solution with explanation

Example: Input: 4->2->1->3 Output: 1->2->3->4 Insertion sort is a comparison based sorting algorithm. In this algorithm we divide the list into 2 parts. The left most part is sorted part, and the right most part is unsorted part. In insertion sort, after each pass at least …