I am trying to construct a algorithm to compare current item in the array with all items to the right of it.
For ex:
[1 2 3 4 5 6 7 8]
I want to compare
- 1 to 2, 1 to 3.....1 to 8
- 2 to 3, 2 to 4.....2 to 8
- 3 t0 4, 3 to 5.....3 to 8
I plan to use Merge sort algorithm to do this O(nlogn) time. Am I am thinking this correctly ?
If using the Merge sort is the right way, I also whether the merge step is still linear ?
Let's take an example: we want to merge [1 2] and R = [3 4]
L = [1 2] and R = [3 4]
My modified merge function compares each element in the left sub-array with each item in the right sub-array : 1 vs 3 ; 1 vs 4 ; 2 vs 3 ; 2 vs 4
The above is a slight deviation from classical merge function where the comparison is just between 1st element of each subarrays
Is the time complexity of the modified merge function still : O(n) as we go up the recursion tree towards the root?
Please advise whether I am going in the right direction or whether there is a better algo ?