How to sort pointers?

[UnknownUsername]

so I have something like:

struct Something
{
int number;
Something* next;
};
And I want to sort them, by the number, though I don't want to change the number, but I want to change the pointer to the next.

How would I do that?

I know the end and the beginning of the "list", (FIFO order)

[Lauke]

Have you tried something like...

1. "Copy" the list cell in an array (linear)
2. Sort the array by the number (n*log n)
3. Once the array is sorted set the pointer of each cell? (linear)

Without auxilary memory i don't think you can do much...

[MiiNiPaa]

Without auxilary memory i don't think you can do much...

Mergesort with inplace merge only needs memory for call stack (as any divide and conquer algorithm)

[Lauke]

I don't get how it could fix the issue of the pointer.
Could you be more specific?

[keskiverto]

Sort uses usually two tools: predicate and swap.

The default predicate is <.
Use > and you get descending order.
With pointers the regular lhs<rhs is not ok; you want to do lhs->number<rhs->number instead.

The default swap is not ok with list either. You have to separate/insert nodes to the list, which involves modifying many nodes/pointers. That sounds complicated.

Take a node from existing list.
Find insertion location in a temporary list. This uses predicate.
Insert node.
Repeat until original list is empty.

[keskiverto]

You need about three pointers of "aux memory".

Pop node from orig.
Find insertion position in temp.
temp.insert(node,pos)
until orig is empty

orig=temp


Edit: Double-post. Thought that the previous post went to bit-heaven.

[Lauke]

Take a node from existing list.
Find insertion location in a temporary list. This uses predicate.
Insert node.
Repeat until original list is empty

What about the computational cost?

Pop node from orig.
Find insertion position in temp.
temp.insert(node,pos)
until orig is empty

Idem above...

Why don't create an array v of Something*, sorting this array on base v[i]->number
and than for each element of the sorted array do v[i]->next = v[i+1]

How much is the access time for the temporary list in your proposal?