Merge 2 sorted lists

Question

I've been asked to come up with as many solutions as possible to the following problem:

Write a function which takes two lists of numbers (both assumed to be in ascending order) and merges them into a single list (also in ascending order).

My first solutions was to append list1 onto list2 and then re-sort.

Then I found a built-in merge.

Then I decided to actually implement a solution myself, and I came up with a tail recursive function that, at the moment, only works for a subset of lists.

The problem itself seems like maybe I finally have a reason to read Knuth, but alas Uni and the Library are closed due to snow.

So I turn to you SO, what are some interesting, or efficient, or anti-pattern approaches to this problem?

---

P.S I'm not looking for implementations, unless thats the best way to demonstrate the idea. I'm just looking to see how people have approached this type of problem.

Answer 1

Merging two sorted lists is algorithmically trivial.

Start with the first element of each list, compare, write the lower one to output and advance the list where you found the lower one. Keep going until you reach the end of one list, then put out the remainder of the other list.

This requires just one loop over each list and max. one comparison per output element.

Edit: This is as efficient as it gets for two lists. It gets (a little bit) trickier when you have a large number of lists to merge.

Answer 2

You could write a function is-sorted-p which determines if the list is still in ascending order. Then concatenate the two lists, and randomly shuffle the result until it passes your predicate.

...you didn't say anything about performance.

Answer 3

If you have exactly two, it's relatively easy.

1. Are both lists empty? If so, the result is an empty list
2. Is one list empty and the other one isn't? The result is the non-empty list.
3. Find the smallest list head ("car"), the result is that list head, consed to the result of a self-call with the tail of that list and the other list.

This can be converted to a tail-recursive process, using some helper parameters (and, possibly, a custom "reverse and cons-onto" helper function).

Answer 4

There are couple of ways to solve this problem.

Since there are two linked lists and since both are sorted the simplest way at a high level ignoring base cases.

list_t*
merge(list_t *head_1P, list_t *head_2P) {

      if (head_1P == NULL) {
             return head_2P;
      } else if (head_2P == NULL) {
             return head_1P;
      }

      list_t *temp = NULL;
      list_t *new_headP = NULL;

      while(head_2P != NULL) {
            // Remove one element from
            // the second list.
            temp = head_2P;
            head_2P = head_2P->next;
            temp->next = NULL;

            insert_sort(&head_1P, temp);
      }
}

void
insert_sort(list_t **headP, list_t *temp) {

      if (*headP == NULL || (*headP)->data > temp->data) {

             temp->next = *headP;
             *headP = temp;
             return;
      }

      list_t *currentP = *headP;

      while(currentP->next != NULL) {

            if (currentP->next->data > temp->data) {

                    temp->next = currentP->next;
                    currentP->next = temp;
                    return;
            }

            currentP = currentP->next;
      }

      temp->next = currentP->next; // Assigning NULL.
      currentP->next = temp;
}

To optimize this further we can make the insert_sort to retun the position where the insertion happened to avoid insertions happening from the begining each time. Because in the worst case this can take O(m*n) time complexity if the second linked list elements all are inserted towards the end of 1st list.

Answer 5

You're looking for a recursive definition of a function that creates a list (by merging two lists).

It is to be expected that the function would create a list by extracting the head element according to some principle, and then recursively constructing the list tail from the remaining elements.

Since you need to return a sorted list, the list head is always the smallest element of the list. So, all you need to do is find an algorithm that extracts the smallest element from two sorted lists (which should be fairly easy, since they're sorted).

Answer 6

If your lists can double as balanced binary trees, you can insert all the elements of list2 to b-tree(list1) and convert back into a list.