Sorting

• Adjacent elements are compared and at the end of first iteration largest element is placed at its correct position i.e last position.
• Next iteration will take place for n-1 elements, i.e last element won’t be included in next iteration.

• Find the smallest element from the array and replace the smallest element found to first position in array. So at the end of first iteration, smallest is placed at its correct position i.e first position
• Next iteration will take place for n-1 elements, i.e first element won’t be included in next iteration.

• In insertion order, we pick each element at a time, and the element picked is compared with existing already sorted elements, and in this way, the new picked element gets its correct position.
• If new picked element is greater than the last element of the already sorted elements, then the new element is already at its correct position.
• This way, in the first iteration itself, we get sorted array through Insertion Sort.

• Merge Sort follows Divide & Conquer approach.
• Merge Sort works by breaking the Array (or Linked List) into 2 equal parts say Left half and Right half.
• Repeat above steps until only 1 element remains in Array (or Linked List) because list with only 1 element is always sorted.
• When complete list is divided and contains only Single element in Left and Right half each,Start comparing and sorting each Left and Right half of the divided array and merge accordingly.

• Heap Sort is build using Binary Heap Data Structure, i.e Complete Binary Tree.
• We build a heap(Max or Min) from the given array elements.
• The root is the max (or min number). So extract it and put it in an array at its proper position.
• Put last element at the root of the tree and Heapify the remaining elements.
• Again extract the root and repeat heapification until there is one element in array.

• In quick sort, we first choose a pivot and divide into two sublists,one will contain elements lower than pivot and other will have elements greater than pivot.
• Recursively sort sublists(sublist with less than pivot, sublist greater than pivot).