1

I want to implement a function that uses an efficient sorting algorithm (mergesort, quicksort), to sort a linked list, with the list being the only parameter. It needs to be consistent with the following function declaration:

void list_sort( list_t* list );

I have looked up many mergesort codes for linked lists, but all of them usually have a head as the parameter, not a list. I am really stuck as to how to solve this. I was thinking perhaps copying all the elements into an array, sorting the array, then copying elements back into the list but was told I cannot do that. If anyone can help, would really appreciate it.

void list_sort( list_t* list ){ 


    //if 0 or 1 element list
    if (list->head==NULL || list->head->next==NULL) {
        return;
    }

    //stuck on what to do after this point
    //I know I need to split the list into two sublists, then recursively call list_sort again
    //then finally merge the two sublists

}

**EDIT: here is list_t 

// List element: a list is a chain of these
typedef struct element
{
  int val;
  struct element* next;
} element_t;

// List header - keep track of the first and last list elements
typedef struct list
{
  element_t* head;
  element_t* tail;
} list_t;
john
  • 57
  • 6
  • 1
    Since you've not shown us what a `list_t` looks like, it is hard to know what your problem is. It is likely to make life easier rather than harder, though. And a merge sort is probably the best choice for sort algorithm. There's a moderate chance that you'll end up with a helper function that takes different arguments, and does the recursive sorting. Your top-level `list_sort simply sets up the recursion. – Jonathan Leffler Mar 25 '19 at 06:08
  • quicksort is probably *bad* because you couldn't use randomization and such which would make the worst-case behaviour bearable. – Antti Haapala -- Слава Україні Mar 25 '19 at 06:11
  • Yea I definitely think quick sort would just overcomplicate everything.. Thanks for the tip – john Mar 25 '19 at 06:26
  • The reason why the sort takes a head as the parameter is that it will then work for recursion. One that takes in `list` cannot be recursive unless you create unnecessary dummy lists for intermediate steps. I.e you'd take *that* algorithm as `do_sort(head)` and have your function `sort(list)` that effectively does `do_sort(list->head)`. – Antti Haapala -- Слава Україні Mar 25 '19 at 06:37
  • So you're saying in the list_sort(list), I should call the function do_sort(list->head), and that way I can implement it recursively? – john Mar 25 '19 at 06:46
  • @john do_sort is a solution – Michael Veksler Mar 25 '19 at 06:53
  • See the duplicate. That also has a link to an implementation of mergesort, http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html – Paul Ogilvie Mar 25 '19 at 08:18

0 Answers0