Data structure - Explain quick sort and merge sort algorithms

Explain quick sort and merge sort algorithms.

Quick sort – Divides the array elements in two halves or partitions. On dividing, the quick sort procedure is recursively called to sort the two halves. A “pivot” is used as the center point and elements less than the pivot are moved to the left or before the pivot and elements greater than pivot are moved to the right.

Merge sort- Merge sort is based on divide and conquer mechanism. The array elements are divided into partitions (n/2). Each partition is sorted recursively and then merged.

Explain quick sort and merge sort algorithms.

Quick sort employs the ‘divide and conquer’ concept by dividing the list of elements into two sub elements

The process is as follows:
1. Select an element, pivot, from the list.
2. Rearrange the elements in the list, so that all elements those are less than the pivot are arranged before the pivot and all elements those are greater than the pivot are arranged after the pivot. Now the pivot is in its position.
3. Sort the both sub lists – sub list of the elements which are less than the pivot and the list of elements which are more than the pivot recursively.

Merge Sort: A comparison based sorting algorithm. The input order is preserved in the sorted output.

Merge Sort algorithm is as follows:
1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Other wise, divide the unsorted list into 2 lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back into one sorted list.

What is merge sort algorithm?

A merge sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence. Run time is T(n log n).

If n<2 then the array is already sorted. Stop now.
Otherwise, n>1, and we perform the following three steps in sequence:
Sort the left half of the the array.
Sort the right half of the the array.
Merge the now-sorted left and right halves.