Sorting, Sorting Set 1, Sorting Set 2
- [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
1. Efficient solution is based on the fact that given array is already sorted.Divide the array into two part “Negative and positive “. Use merge function to merge two sorted arrays into a single sorted array.
Time complexity: O(n) space complexity: O(n)
2. Sort the array. Time complexity : O(n log n)
- [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
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)
- ***** [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. Enhance Merge Sort. Time Complexity: O(nlogn)
Similar: Find Surpasser Count of each element in array. GFG
[Comparator] Sort an array of integer where the integer are very large and they need to be stored at string. Code
Similar: Given an array of dates, how to sort them.
and Sort an array according to count of set bits
Both of these make use of Comparator along with default built in sort method.
- *** Sort an array of 0s, 1s and 2s Given an array A consisting 0s, 1s and 2s, write a function that sorts A. The functions should put all 0s first, then all 1s and all 2s in last. GFG