Sort a list by an ordered index

Question

Let us assume that I have the following two sequences:

val index = Seq(2,5,1,4,7,6,3)
val unsorted = Seq(7,6,5,4,3,2,1)

The first is the index by which the second should be sorted. My current solution is to traverse over the index and construct a new sequence with the found elements from the unsorted sequence.

val sorted  = index.foldLeft(Seq[Int]()) { (s, num) => 
  s ++ Seq(unsorted.find(_ == num).get)
}

But this solution seems very inefficient and error-prone to me. On every iteration it searches the complete unsorted sequence. And if the index and the unsorted list aren't in sync, then either an error will be thrown or an element will be omitted. In both cases, the not in sync elements should be appended to the ordered sequence.

Is there a more efficient and solid solution for this problem? Or is there a sort algorithm which fits into this paradigm?

---

Note: This is a constructed example. In reality I would like to sort a list of mongodb documents by an ordered list of document Id's.

---

Update 1

I've selected the answer from Marius Danila because it seems the more fastest and scala-ish solution for my problem. It doesn't come with a not in sync item solution, but this could be easily implemented.

So here is the updated solution:

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = {
  val positionMapping = HashMap(index.zipWithIndex: _*)
  val inSync = new Array[T](unsorted.size)
  val notInSync = new ArrayBuffer[T]()
  for (item <- unsorted) {
    if (positionMapping.contains(key(item))) {
      inSync(positionMapping(key(item))) = item
    } else {
      notInSync.append(item)
    }
  }

  inSync.filterNot(_ == null) ++ notInSync
}

---

Update 2

The approach suggested by Bask.cc seems the correct answer. It also doesn't consider the not in sync issue, but this can also be easily implemented.

val index: Seq[String]
val entities: Seq[Foo]
val idToEntityMap = entities.map(e => e.id -> e).toMap
val sorted = index.map(idToEntityMap)
val result = sorted ++ entities.filterNot(sorted.toSet)

Answer 1

Why do you want to sort collection, when you already have sorted index collection? You can just use map

Concerning> In reality I would like to sort a list of mongodb documents by an ordered list of document Id's.

val ids: Seq[String]
val entities: Seq[Foo]
val idToEntityMap = entities.map(e => e.id -> e).toMap

ids.map(idToEntityMap _)

Answer 2

This may not exactly map to your use case, but Googlers may find this useful:

scala> val ids = List(3, 1, 0, 2)
ids: List[Int] = List(3, 1, 0, 2)

scala> val unsorted = List("third", "second", "fourth", "first")
unsorted: List[String] = List(third, second, fourth, first)

scala> val sorted = ids map unsorted
sorted: List[String] = List(first, second, third, fourth)