Introduction

This problem is often called relative sorting. You have one array, arr1, that you want to reorder, and another array, arr2, that defines the preferred order for some values. Elements that appear in arr2 should come first in that exact order, and values not mentioned in arr2 should usually be placed afterward in normal sorted order.

The Core Idea

The simplest solution is to build a priority map from arr2.

For example, if:

• 'arr1 = [2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8]'
• 'arr2 = [2, 1, 8, 3]'

then the priority map is:

• '2 -> 0'
• '1 -> 1'
• '8 -> 2'
• '3 -> 3'

Any value found in that map should be sorted by its mapped priority. Any value not found should be placed later and sorted naturally.

Python Implementation

1def relative_sort(arr1, arr2):
2    order = {value: index for index, value in enumerate(arr2)}
3
4    return sorted(
5        arr1,
6        key=lambda x: (0, order[x]) if x in order else (1, x)
7    )
8
9arr1 = [2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8]
10arr2 = [2, 1, 8, 3]
11
12print(relative_sort(arr1, arr2))

Output:

[2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9]

The tuple sort key does all the work:

• values from arr2 get group 0 and a priority index
• values not in arr2 get group 1 and are ordered by their own value

Why This Works

The sort key imposes two layers of ordering:

1. whether the element appears in arr2
2. what its rank or natural value is inside that group

That makes the rule explicit and easy to extend.

An Alternative Counting Approach

If the values are simple and duplicates matter heavily, another good solution is counting frequencies.

1from collections import Counter
2
3def relative_sort_counting(arr1, arr2):
4    counts = Counter(arr1)
5    result = []
6
7    for value in arr2:
8        result.extend([value] * counts.pop(value, 0))
9
10    for value in sorted(counts):
11        result.extend([value] * counts[value])
12
13    return result

This approach is especially nice when you want full control over duplicate handling.

Time Complexity

The custom-sort solution typically runs in O(n log n) because it still relies on sorting arr1.

The counting version can be attractive when the number of distinct values is small relative to the total array size, but the right choice depends on the data and language.

In interviews, the custom-sort answer is usually enough because it is easy to explain and easy to verify. In production code, choose the version that your team will read correctly six months later. For most languages, clarity matters more than shaving a small constant factor from a relative-sort utility.

Common Pitfalls

A common mistake is forgetting to decide what happens to values in arr1 that are not present in arr2. Most versions of the problem want them sorted normally at the end.

Another mistake is using an order map but not handling duplicates carefully. The priority map tells you where a value belongs, but duplicates still need to be preserved in the result.

A third issue is assuming arr2 contains every possible value. Many real inputs do not, so the fallback ordering matters.

Summary

• Build a priority map from the reference array arr2
• Sort arr1 so referenced values come first in arr2 order
• Place values not in arr2 afterward using normal ordering
• A tuple sort key is a clean Python solution
• Counting frequencies is another good option when duplicates are important