Le_Forgeron <lef### [at] free fr> wrote:
> If instead of a single value, the cells of your array contains also a
> pointer to the next value in the list, you could sort it without moving
> the value, and only updating the "next" index field.
How would you find the proper place for the value faster than O(n)?
Performing insertion sort on a linked list is still O(n^2) even though
the insertion itself can be done in constant-time. That's because finding
the point of insertion takes O(n) time.
--
- Warp
Post a reply to this message
|