Algorithm for ordering a list based on the ordering of another, partial, list

You can accomplish what you want by setting up a custom comparator as Dennis Callanan has suggested and then doing a stable sort of the array. Quicksort is not a stable sort; it will generally change the order of elements not included in the partial ordering. Merge sort is a stable sort.

If you use linear search in the comparator, the algorithm will run in time O(n^2 log n) I think. What you need to do to make it run faster is to make one run through the new array, hashing the position of each element in the array for fast lookups.

I could implement it in Java but I don't know Python, sorry.

Another perspective on this is to use a topological sort. In your original list you had a -> b -> c -> d -> e where the arrows mean a "comes before" b. Then you add the new data b -> e -> d. You've got to break any arrows in the first list that lead to contradictions, i.e., d -> e. What you then have is a bunch of arrows:

a -> b, b -> c, c -> d, b -> e, e -> d

If that is a directed acyclic graph (i.e., no contradictions), you can then toposort it in O(V + E) time. Since the number of edges is at most 2n, that's O(n) time, very efficient.

The issue is deciding what arrows to break (and maybe replace with other arrows) in the original list so that there aren't any contradictions. In general that's an NP-hard problem called minimum feedback arc set but I suspect there's something in the structure of your problem that would make it run faster.

Finally, what about just replacing the elements in the (non-contiguous) subarray [ ..., b, ..., d, e] with the permutation given by the new array? That can be accomplished in O(n) time.

One naive n^2 approach is:

for each S in order-list
  if S is in other-list
     remove S from other-list
     add S to end of other-list

Which will result in the items from your sort-list being removed and appended to your other list: [a, c, b, e, d]

I wrote a version of quicksort for fun for another question (Javascript Double sorting algorithm), which I have no idea if it is fully reliable. It was originally meant to sort just the strings or just the numbers but seems adaptable to this case (I changed the "isNumber" and "less" functions):

function isNumber(x,y) {
  return (map[x]);
}

function less(a,b,y){
  return y ? a < b : map[a] < map[b];
}

function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; }

function partition(array, pivot, left, right, what) {
  var store = left,
      pivotValue = array[pivot];

  swap(array, pivot, right);

  for (var v = left; v < right; v++) {
    if (less(array[v],pivotValue,what) && isNumber(array[v],what)) {
      swap(array, v, store);
      store++;
    }
  }

  while(!isNumber(array[store],what))
    store++;

  swap(array, right, store);

  return store;
}

function doubleQSort(array, left, right, what) {
  while(!isNumber(array[right],what) && right > left)
    right--;
  while(!isNumber(array[left],what) && left < right)
    left++;

  var pivot = null;

  if (left < right) {
    pivot = (right + left) >> 1;

    while(!isNumber(array[pivot],what))
      pivot--;

    newPivot = partition(array, pivot, left, right, what);

    doubleQSort(array, left, newPivot - 1,what);
    doubleQSort(array, newPivot + 1, right,what);
  }
}

Output:

var things = ['a', 'b', 'c', 'd', 'e'];
var map = {'b':1, 'e':2, 'd':3}

doubleQSort(things,0,things.length - 1);
console.log(things) // [a, b, c, e, d]

Python approach, easily implemented in any language (Java won't require functools)

import functools

order = [5, 1, 4]

def numeric_compare(x, y):
    if x in order and y in order:
        if order.index(x) > order.index(y):
            return 1
        elif order.index(x) < order.index(y):
            return -1
    else:
        if x in order:
            return -1
        elif y in order:
            return 1
    return 0

a = [1,2,3,4,5]
a.sort(key = functools.cmp_to_key(numeric_compare))