Bottom up merge sort on Linked List <p>Bottom up merge sort treats a list each element of size 1, and iteratively merge the sub-lists back and forth until they are in sorted order. This makes it very attractive to use bottom up merge sort to sort linked list as they are already "separated".</p> <p>I'm trying to implement bottom up merge sort in C language, and realised that there are various approach to implement bottom up merge sort; in particular, I'm using this approach: </p> <ol> <li>Insert single lists into a queue</li> <li>Dequeue first two lists and merge them</li> <li>Enqueue merged lists (merged items go to the end)</li> <li>Repeat step 1-3 until they are in sorted order</li> </ol> <p>However, I'm struggling to implement the following:</p> <ul> <li>Merge linked-lists without using extra O(n) space (if possible)</li> </ul> <p>Hence, my questions are: </p> <ul> <li><strong><em>How would one implement</em></strong> this correctly in C language? (in particular: the handling of repeating the <strong><em>dequeue and enqueue process until it's fully sorted</em></strong>) How would one know if the entire queue is in sorted order? I'm thinking of keeping track of the *head pointer(s) in a list.</li> <li><strong><em>Is merge sort stable in this case? Why?</em></strong> </li> <li>The running time of bottom-up merge sort is still O(nlogn). However, <strong><em>does this bottom up merge sort use O(n) space</em></strong>? Suppose the linked-list we implement is already a queue. </li> <li>Extra question: is there a better alternative to implement bottom-up merge sort on linked list? </li> </ul> <p>I suppose this is one of the advantage of using bottom-up merge sort on linked list, as it is more space efficient than using bottom-up merge sort on arrays. Correct me if I'm wrong.</p>