Question

8. In plain English, explain how Mergesort, and QuickSort algorithms work and give your reasons why QuickSort is considered to be the fastest algorithm in practice even so the Mergesort runs always as Θ(MogN) and Quicksort as θ(NlogN) only on average while for some inputs can run as long as o(N-)? 9. On simple examples, explain how quadratic probing works and why it can fail if a hash table is over half full.

Answer 1

Sol. 1. Quicksort Algorithm is basically a divide and conquer rule based algorithm. Divide and conquer means dividing the given array (data structure type ) and divide until it will become sort.

These are the below steps which we perform while doing the Quicksort :

Step 1. Pick the first element as pivot . Similarly for last , random and median pivot will be selected.

Step 2. Quicksort left halves.

Step 3. Quicksort right halves.

These all are recursive steps untill the sorting will not be completed.

The pivot which we selected will be at the center of the array and we will start putting other elements in a specific pattern.Such as the Smaller elements can be on before the pivot and the greater elements can be after pivot . This all will be done in linear timeframe.

MergeSort Algorithm

MergeSort Algorithm is also based on the Divide and Conquer algorithm. It basically divides the array which is an input into two parts or different array and then after sorting these smaller arrays, it merge the two smaller parts and hence the sorting will be achieved.

Here is a function called as merge() which we use for this algorithm processing:

MergeSort(arr[], left , right) If right > left

1. Finding the middle point of the array so can divide into two parts.

middle m = (left + right)/2

2. Now call mergeSort on the first part

Call mergeSort (arr, 1, middle)

3. Now call mergeSort on the second part

Call mergeSort (arr, m+1, right)

4. now merge the both two sorted parts

Call merge (arr, left, middle, right)

Hence we get the below conclusions and based on these we can decide which sorting is faster:

1. MergeSort basically divide the input array into two parts and then perform sorting so it's better in case of larger arraysize or datasets while Quicksort divide the input array into n smaller arrays and sort so it's better for the smaller aaraysize or dataset.

2. While performing the operation the Quicksort store the data in the main memory while the mergeSort uses the secondary memory of the system. Using Secondary memory or external memory will be expensive as compared with the internal always.

3. If we talk about the complexities the Quicksort worst case complexity is O(n2) while the mergeSort has same complexity for worst case and average case which is O(n log n )

Hence , we can say that MergeSort is best for the larger datasets and Quicksort is good for the smaller dataset.

Let me know in case of any query.

​​​​