I need to make a pivot sorting algorithm where essentially you take the first item of a linked list, sort it into two separate lists one with items greater than or eual to the first item, and one with items less than the first item, then sort them recursively until you reach a linked list of size 1 where it is already sorted, then just merge together the lesser and greater than lists to form a sorted list.

My algorithm keeps getting stuck on the last item in an infinite loop and I've been without sleep now for about 23 hours and need a fresh pair of eyes to spot where I'm making the mistake. If you could help out I would be much obliged.

The Linked list class is simple, two items, first is just a positive integer, second is of course the next item in the list. The code gets caught in the Sort() function when it hits the last item and doesn't then append the last items together

Never mind, I needed to always append teh first item in the Part_Greater call and call everything after it.
Code:
``````public class PivotSort{

public static void main(String[] args) {
try{

intList x =     intList.CreateFromUserInput(); // just makes a linked list from numbers I type in
x = Sort(x);
x.PrintList();
}
catch (Exception e)
{
System.out.println(e);
}

}
public static intList Sort(intList list)
{
if (list == null || list.item == null)
return list;
return Append(Sort(Part_Less(list.item, list)), Sort(Part_Greater(list.item, list)));

}

public static intList Part_Less(int N, intList L1)
{
if(L1 == null)
return null;
if(L1.item < N)
return new intList(L1.item, Part_Less(N, L1.next));
else
return Part_Less(N, L1.next);
}
public static intList Part_Greater(int N, intList L1)
{
if(L1 == null)
return null;
if(L1.item >= N)
return new intList(L1.item, Part_Greater(N, L1.next));
else
return Part_Greater(N, L1.next);
}

public static intList Append(intList L1, intList L2)
{
try{
if(L1 == null)
return L2;
if(L2 == null)
return L1;

for(intList curr = L1; curr!=null; curr=curr.next)
{
if(curr.next == null)
{
curr.next = L2;
break;
}
}
return L1;
}
catch(Exception e)
{
System.out.println(e);
return null;
}

}

}```
```

Edited by ZTR1760 - 11/3/12 at 4:05pm
 OC Beast (13 items)
CPUMotherboardGraphicsRAM
E8500 @4GHZ Gigabyte P45 4850x2 2GB IT LIVES! 4GB
Hard DriveOptical DriveOSMonitor
500AAKS+250external CD-DVD combo windows 7 ultimate x64 26"
KeyboardPowerCaseMouse
MC\$ wireless 650w corsair antec 900 Logitech battlefield 2142 G5
 OC Beast (13 items)
CPUMotherboardGraphicsRAM
E8500 @4GHZ Gigabyte P45 4850x2 2GB IT LIVES! 4GB
Hard DriveOptical DriveOSMonitor
500AAKS+250external CD-DVD combo windows 7 ultimate x64 26"
KeyboardPowerCaseMouse
MC\$ wireless 650w corsair antec 900 Logitech battlefield 2142 G5