Sorting – Set 3

1. [Merge Sort] Sort array after converting elements to their squares Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array. GFG
Algo:
1. Since half of the array is positive and negative, when we square each element, the resulting array will be like a parabola equation, i.e. about a pivot the array will be sorted in descending order and in the other half it will be ascending order. So here we have two sorted array. This is a proper candidate for merge sort. We just need to merge these two array.
Time complexity: O(n)
Space complexity: O(n)
2. Sort the array.  Time complexity : O(n log n)

2. [Merge Sort] Sort an array when two halves are sorted. Given an integer array of which both first half and second half are sorted. Task is to merge two sorted halves of array into single sorted array. GFG. Same logic as previous question.
Algo:
1.Sort the complete array. Time Complexity O(nlogn)
2.
An efficient solution is to use an auxiliary array one half. Now whole process is same as the Merge Function of Merge sort.Time Complexity : O(n)

3. ***** [Merge Sort]  Count Inversions in an array. GFG
1. For each element, count number of elements which are on right side of it and are smaller than it.
Time Complexity: O(n^2)
2. [Pending] Enhance Merge Sort.
Time Complexity: O(nlogn)
Similar: Find Surpasser Count of each element in array. GFG

4. *** Merge Sort for Linked Lists. GFG
Algo:
The base case
for the recursive merge method will be that the node or node.next is null. If this is not the case then we find the middle of the linked list using the two pointer method. This method will return reference to the middle node in the list.
Now we need to split the linked list around this point.
So we save middle.next and then set middle.next = null.
Now that the list has two part, we call the recursive method.
node middle = getMiddle(h);
node nextofmiddle = middle.next;
middle.next = null;
node left = mergeSort(h);
node right = mergeSort(nextofmiddle);
node sortedlist = sortedMerge(left, right);
return sortedlist;
The sortedMerge() will be implemented recursively as unlike array we can’t access random element in linked list.