Questions about sorting


I am studying sorting in an algorithm course. I need a hint because I really don’t know where to start with these two following questions. Any help is appreciated.

Suppose all integers are stored in a single linked list.

  1. Write a function Sort whose input is a pointer to the first node of a list of unknown length.

    List Sort(node *head)

    Your method should return its elements in a sorted list. Again, your method should not create any new nodes and should have time complexity O(nlogn).

  2. Suppose two (unsorted) arrays A[0…n – 1] and B[0…n – 1] together contain 2n distinct numbers. Describe a method to construct an array C[O..n – 1] such that for each index i E [O..n -1], A[i] is greater than exactly C[i] elements in the array B[0…n – 1]. Your method may use O(n) extra space and should have O(nlogn) running time.