Sorting

• Quick Sort: Uses Divide/Conquer technique to solve. Take a pivot (left, right, mid or any). Idea is need to find the position of the pivot in the array. How: Take 2 pointers i & j, here pivot’s left-side elements should be smaller/equal and right-side elements should be greater/equal. If the ith element is smaller than pivot, increment i, same for j, until the condition fails. After that, swap the i and j, and move on until i crosses j. So after we found position of the pivot i.e., j so swap with pivot original position (which taken at start) with jth position.
• Merge Sort: Similar to Quick sort, but uses extra space. Here we take mid as pivot, and recursively break the array into smaller parts in mid, and once there are 1 or no elements in the array, we sort them and return. after returning to call stack, the merge phase occurs, here we need to create a new array and put the elements accordingly.