Le_Forgeron <lef### [at] freefr> 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