# Sort an Given Array in the order defined by another array

**Objective:** Given an array of integers, write an algorithm to sort it according to the order defined by another array.

**Input:** An Array of Integers

**Example**:

Input Array : 2 6 9 1 4 4 2 1 10 13 5 7 8 DefinedArray : 1 2 4 6 Output : 1 1 2 2 4 4 6 5 7 8 9 10 13

**Appraoch:**

**Method 1: Sort and Search**

- Create an Aux array and copy all the elements of arrA
- Create another boolean array, visited[] of size arrA[]
- Initialize visited[] = false
- Sort the Aux array using Merge sort.
- Navigate through the arrB, taking one element at a time, say x
- perform binary search of x on Aux array and find the first occurrence of x
- if x is found, copy it to arrA, make visited[] = true
- Do linear navigation on Aux array till you find x, copy all these to arrA and mark visited[] = true
- When arrB is over, copy rest of the elements from Aux to arrA.

**Method 2: Using Hashing**

- Insert all the elements of arrA in hash Table,
- Element as key and its count as its value
- Navigate through arrB, check element’s presence in Hash table
- If it is present then takes its value (count) and insert into arrA.
- Once arrB is completed, take rest of the elements from Hash table
- Sort Them and insert into arrB.

**Complete Code for both methods:**

**Output:**

Original Array : 2 6 9 1 4 4 2 1 10 13 5 7 8 Defined Array : 1 2 4 6 Output Array using Sort and search: 1 1 2 2 4 4 6 5 7 8 9 10 13 Output Array using Hashing : 1 1 2 2 4 4 6 5 7 8 9 10 13