I am currently pondering how to efficiently design an algorithm for a sorting problem and hope that someone here may help me out a bit.
I have two lists of integers, let's call them the 'input' list and the 'position' list, and want to sort the 'input' list based on the position of each 'integer' in the position list. Which algorithm could I use to achieve this in the most efficient manner possible?
This Question assumes the following:
- accessing a list element by index and/or calculating the length of a list is possible in
- the input list has
kelements and the position list
nelements. Both lists contain each element at most once, but may contain elements not in the other list.
nwill usually be greater than
- The behavior for elements present in the input list but not the position list is not important, but must be consistent (e.g. all sorted to the start). Discarding the integers not present in the other list is acceptable, but suboptimal. Integers present in the position list but not in the input list must be ignored.
- the input list is sorted by the integers themselves (lowest integer first), the position list is sorted by an unknown criteria
- 'efficiency' refers to both runtime complexity and memory complexity, but runtime complexity is more important
Example of the problem
Here is an example of the problem I am trying to solve:
input_list = [1, 3, 5, 7, 11, 13] # the list to sort position_list = [5, 6, 7, 1, 11, 12, 13, 3] # the order of elements sorted_list = sort_by_position(input_list, position_list) print(sorted_list) [5, 7, 1, 11, 13, 3]
So far I've identified the following solutions:
- Simply using a regular sorting algorithm (e.g. merge sort, quick sort, ...), using a simple linear (
O(n)) algorithm to determine the position of each element in the position list as comparison key. Even using the merge sort sorting methods this would be
O(k * log(k) * n)at best.
- Iterating over the position list and utilizing binary search on the input list to determine presence of the elements in the input list, inserting each found element one after another. This could achieve
O(n * log(k)), which is better.
I believe that there is probably potential for improvement here and would appreciate your help.