advanced sorting merge sort the merge sort algorithm is an excellent choice for sorting linked list unlike the sequence-based versionwhich requires additional storagewhen used with linked list the merge sort is efficient in both time and space the linked list versionwhich works in the same fashion as the sequence versionis provided in listing listing the merge sort algorithm for linked lists sorts linked list using merge sort new head reference is returned def llistmergesortthelist )if the list is empty (base case)return none if thelist is none return none split the linked list into two sublists of equal size rightlist _splitlinkedlistthelist leftlist thelist perform the same operation on the left half leftlist llistmergesortleftlist and the right half rightlist llistmergesortrightlist merge the two ordered sublists thelist _mergelinkedlistsleftlistrightlist return the head pointer of the ordered sublist return thelist splits linked list at the midpoint to create two sublists the head reference of the right sublist is returned the left sublist is still referenced by the original head reference def _splitlinkedlistsublist )assign reference to the first and second nodes in the list midpoint sublist curnode midpoint next iterate through the list until curnode falls off the end while curnode is not none advance curnode to the next node curnode curnode next if there are more nodesadvance curnode again and midpoint once if curnode is not none midpoint midpoint next curnode curnode next set rightlist as the head pointer to the right sublist rightlist midpoint next unlink the right sub list from the left sublist midpoint next none