Hi I am making a custom linked list (for fun!) and want to implement a sort method that sorts the stored data using the stored types > and < operators (will require the type to have these operators overloaded)
What is the best way to do this? I guess the first thing one might jump to would be to compare the current node with the the node to its "right" see if one is greater than the other. Then keep iterating through the list until you don't swap any more nodes. However I am thinking there is probably a more efficient way to do this. Here is my code so far:
What you are asking for is O(n) time complexity. This is not even possible for data which is contiguous in memory. There are some algo's though which can give O(n) complexity but they are not practical for production environments.
Here you have a linked list which has nodes scattered in memory. generally the sort take O(n^2)time complexity for a linked list. This can be marginally improved (reducing the constant factor may be). What you can do is use a external data structure may be a tree or hash table and keep some metadata in that (sorted) which will map to the actual linkedlist.