4
\$\begingroup\$

This is an implementation of a singly linked list merge sort I did on paper during a job interview recently, using a bottom-up approach.

The requirement was simply "implement a merge sort for a singly linked list whose last node is indicated by a null value in its next pointer. An empty list is simply a null pointer to a node."

After having reviewed the code, the company decided I wasn't fit for their needs, but didn't want to disclose what in the code wasn't up to their standards. They however stressed that they not only care about whether the program works, but also whether it's elegant and easy to read.

I used a bottom-up approach because of its in-place merging abilities that make it optimal in space: O(1).

Would anybody tell me what is possibly wrong with my implementation and how it could be improved?

template <typename T>
struct Node {
    Node *next;
    T data;
};

template <typename T>
Node<T> **skip(Node<T> **pN, size_t s) {
    while (s-- && *pN)
        pN = &(*pN)->next;

    return pN;
}

template <typename T>
void insert_before(Node<T> **pAfter, Node<T> *n) {
    n->next = *pAfter;
    *pAfter = n;
}

template <typename T>
Node<T> *remove(Node<T> **pN) {
    Node<T> *n = *pN;
    *pN = n->next;
    n->next = 0;

    return n;
}

template <typename T>
Node<T> **merge_two_first_sublists(Node<T> **pN, size_t s) {
    Node<T> **pLeft = pN;
    Node<T> **pRight = skip(pN, s);

    while (*pRight && s != 0 && pLeft != pRight) {
        if ((*pRight)->data < (*pLeft)->data) {
            insert_before(pLeft, remove(pRight));
            --s;
        }    
        else        
            pLeft = &(*pLeft)->next;
    }

    return skip(pRight, s);
}


template <typename T>
Node<T> *merge_sort(Node<T> *n) {
    size_t s = 1;
    size_t l;

    do {
        Node<T> **pNextFirst = &n;

        for (l = 0; *pNextFirst; ++l)
            pNextFirst = merge_two_first_sublists(pNextFirst, s);

        s *= 2;
    } while (l > 1);

    return n;
}

I can see one obvious small change: merge the remove() and insert_before() functions into one move_before() function, which would make the n->next = 0; line in the remove() function unnecessary, but do you think it's worth it?

Another change could be to use int rather than size_t, as many nowadays generally consider it harmful to use unsigned integers, but given that the type is used only internally by the merge algorithm itself and that underflows are guaranteed to not happen, is that an issue worth targetting?

A compile-and-run version on coliru: http://coliru.stacked-crooked.com/a/81638c30d4bc524f

\$\endgroup\$
2
\$\begingroup\$

For what it's worth, I feel your pain about not getting any useful feedback from an interview. At least they actually told you that you didn't get the job! I've had companies (very well known, well-respected companies) not contact me to let me know I didn't get the job. In any event, here are some improvements that I think you could make.

Naming

Your functions are named reasonably well, but your variables are not. Instead of pN, just write node. Instead of s, write size or length. It will make your code far easier to read. Also, Hungarian notation (prefixing variables with a letter to indicate type) is out-of-fashion. Even if it weren't, I'm not sure you've done it correctly. A pointer to a pointer to a node should be ppN, not pN, shouldn't it?

The name merge_two_first_sublists() is really confusing. Why are they called first? And why don't you pass the function 2 lists? Even if you implement it in O(1) space, you can still pass in the pointer to each list. And if you do it that way you can use it even for lists that aren't contiguous.

In merge_sort() you have a variable simply named l. This is a dangerous name. In many fonts, it looks like a numeral 1. In general 1-letter variable names are a bad idea. I can give a pass for loop counters i and j, but beyond that, you should really avoid them.

Classes

You're programming in an object-oriented language, but you aren't using objects, which is a little odd. Why aren't insert_before(), remove() and skip() methods on a List class? It's not clear to me from the requirements you posted that it wouldn't be acceptable to do it that way. It would encapsulate the list in a convenient way and protect it from being modified elsewhere.

Overuse of Pointers

C++ has a lot of ways to avoid using pointers. The reason it has them is because pointers are extremely error prone and code that uses raw pointers is a maintenance headache. You've doubled-down on pointers and are using pointers-to-pointers in every function. It doesn't look to me like you need them in most of the functions. For example, why can't skip() be written like this:

template  <typename T>
Node<T> *skip(Node<T> *pN, size_t s) {
    while (s-- && pN)
        pN = pN->next;

    return pN;
}

What do you gain by using a pointer to a pointer?

How does insert_before() even work? The first argument is a pointer-to-a-pointer to the node we wish to insert after the second argument, n. So we have to end up with n->next assigned to the address of the "after" node. Don't we also need to have the "after" node's next pointer pointing to whatever n->next was pointing to before the call? I don't see that happening anywhere. And for the life of me, I can't figure out what the last line of the function is doing. Why do you set the pointer that was pointing to the pointer to the "after" node to point to the "before" node? What does that accomplish?

Why does remove() return anything? I wouldn't expect a remove() function to return any value. I'd just expect it to remove the node in question from the list. But it doesn't even take a list an as argument, just a pointer to a pointer to a node. This is going to be difficult to use and maintain, in my experience.

I recommend avoiding pointers at all if you can. In C++ you can use references instead of pointers in many cases. With C++11 and later, you can use shared_ptr and unique_ptr where appropriate. The requirements do say that the list uses pointers, so at least encapsulate them as best you can. If you have to have a function that modifies a pointer that's an argument you can pass in a reference to a pointer instead of a pointer to a pointer.

\$\endgroup\$
0
\$\begingroup\$

The skip function incurs some overhead, but so would a top down merge sort that scans a linked list for the mid point.

A basic 2 way bottom up merge sort would use 4 lists, or more specifically 4 pointers to the first nodes of the 4 lists. The initial list is split into two lists, where each "run" has a size of 1 node, then runs from each of the two lists are merged and alternately appended to each of the output lists. Calling the lists A, B, C, D, then one run each from A and B are merged into C, then the next pair of runs merged into D, repeating this process until A and B are emptied. Then the pointers are swapped to merge runs from C and D alternately into A and B. This process is repeated until a single sorted list is produced.

A non-obvious bottom up solution is to use a small (26 to 32) array of pointers as lists, where each successive pointer in the array points to a list that doubles in size. This is probably the fastest way to sort a linked list short of copying the list to an array or vector, sorting the array or vector, then creating a new list from the sorted array or vector. The wiki article for merge sort explains this with pseudo code:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Note that the most elegant solutions are not always the simplest to read.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.