🔢 Mastering Relative Sorting in Java (With Java 8 Best Practices)

Sorting an array based on another array's order is a popular coding problem seen in interviews and real-world systems where custom sorting logic is required.

---

🧩 Problem Statement

You're given two arrays:

• arr1: The array you need to sort.

• arr2: Specifies the relative ordering of some elements.

📌 Sort Rules:

1. Elements from arr1 that are in arr2 appear first, in the same order as in arr2.

2. Remaining elements (not in arr2) are sorted in ascending order.

---

✅ Example

Input:
arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]

Output:
[2,2,2,1,4,3,3,9,6,7,19]

---

🧪 Approach 1: Counting Sort (Optimal if Range is Known)

✅ Code:

public int[] relativeSortArray(int[] arr1, int[] arr2) {
    int[] count = new int[1001]; // assume elements are in 0–1000 range
    for (int num : arr1) count[num]++;

    int[] result = new int[arr1.length];
    int i = 0;

    for (int num : arr2)
        while (count[num]-- > 0)
            result[i++] = num;

    for (int num = 0; num < count.length; num++)
        while (count[num]-- > 0)
            result[i++] = num;

    return result;
}

✅ When to Use:

• You know the range of input (e.g., 0 to 1000).

• Performance is critical (time complexity: O(n + m + k)).

• Memory usage is acceptable for fixed range.

🧠 Tips:

• Preallocate frequency arrays if range is predictable.

• Avoid using this for values outside a known range (e.g., negative numbers, large integers).

---

🌟 Approach 2: Java 8 Functional Solution (Elegant & Flexible)

✅ Code:

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) indexMap.put(arr2[i], i);

        List<Integer> list = Arrays.stream(arr1).boxed().collect(Collectors.toList());

        list.sort((a, b) -> {
            if (indexMap.containsKey(a) && indexMap.containsKey(b))
                return Integer.compare(indexMap.get(a), indexMap.get(b));
            else if (indexMap.containsKey(a))
                return -1;
            else if (indexMap.containsKey(b))
                return 1;
            else
                return Integer.compare(a, b);
        });

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

✅ When to Use:

• You want a cleaner, more readable solution.

• The input range is unknown or unbounded.

• You’re working in a modern Java codebase that uses Streams and Lambdas.

---

🧠 Best Practices & Tips

Practice	Tip
🔢 Choose Right Approach	Use counting sort for known integer ranges. Use Java 8 functional approach for readability and flexibility.
♻️ Avoid Magic Numbers	Use Integer.MAX_VALUE or define range constants instead of hardcoding 1001.
🔍 Handle Edge Cases	Always account for: duplicates, missing values in arr2, or values in arr2 not present in arr1.
⚙️ Immutable Data	Prefer working with immutable streams when functional clarity matters.
🔄 Convert Safely	Use boxed() and mapToInt() to safely convert between primitives and wrappers.
🚀 Optimize for Large Input	Counting sort is more performant than stream sorting when input size is large and value range is small.
🧪 Unit Testing	Cover edge cases like arr2 being empty, all values in arr1 being outside arr2, etc.

---

📚 Summary

Feature	Counting Sort	Java 8 Functional
Input Range Required	✅ Yes (e.g., 0–1000)	❌ No
Duplicates	✅ Handled	✅ Handled
Readability	❌ Medium	✅ High
Performance	✅ Faster for small range	❌ Slightly Slower
Suitable for Interviews	✅ Yes	✅ Yes (bonus if explained well)

---

🧑‍💻 Final Thoughts

Both approaches are valid and useful depending on your context:

• For interview coding rounds, start with the counting sort for performance, then mention the Java 8 version as a cleaner alternative.

• For production code, prefer the Java 8 solution unless performance is critical and the input range is tightly controlled.