Linked Lists - A Concise and Practical Introduction to Programming Algorithms in Java - page 159

half and create from it two linked lists, say u1 and u2 . Recursively sort both
sub-lists u1 and u2 of roughly half size, and merge them using the previous
recursive merging function. To split in half the source list u , we first compute
the length of u and set u2 to the cell split met half way. We also need to create
the tail of u1 by explicitly setting the next field of the previous cell (that we
call prevSplit )to null . Overall the sorting code for linked list is given below:

Program 7.17 Recursively sorting an arbitrary linked list
static List sortRec(List u)
int l=Length(u) ;

if (l < =1)
return u;
else
{ int i, lr;
List u1, u2, split , prevSplit ; // references to cells

u1=u ;
prevSplit=split=u;
i=0;lr=l /2;

while (i < lr)
{ i ++;
prevSplit=split ;
split=split .next; }

u2=split ; // terminates with a null
prevSplit . next= null ; // ensure u1 terminates with a null

return mergeRec( sortRec(u1) , sortRec(u2) ) ;
}

}

Let u be the following linked list:

20 −− > 19 −− > 21 −− > 23 −− > 17 −− > 15 −− > 1 −− > 6 −− > 9 −− > 2 −− > 3 −− > null

Then executing the following code...

u.Display() ;
List sortu=sortRec(u) ;
System . out . println ( "Sorted linked list:" );
sortu . Display () ;

...will return the sorted linked list:
1-->2-->3-->6-->9-->15-->17-->19-->20-->21-->23-->null

Once again, we have only recycled the previously created cells by changing their
next field. Procedures sortRec and mergeRec do not create new cell objects.