Difference Between Quick Sort and Merge Sort
A sorting is the arrangement of collectively data in particular format like ascending or descending order. Generally, it is used to arrange the homogeneous data in sorted manner. Using the sorting algorithms, we can arrange the data in a sequence order and search an element easily and faster. Sorting techniques depends on two situation such as total time and total space required to execute a program. In this section, we will discuss quick sort and merge sort and also compare them each other.
Quick Sort
Quick sort is a comparison based sorting algorithm that follows the divide and conquer technique to sort the arrays. In quick sort, we usually use a pivot (key) element to compare and interchange the position of the element based on some condition. When a pivot element gets its fixed position in the array that shows the termination of comparison & interchange procedure. After that, the array divides into the two sub arrays. Where the first partition contains all those elements that are less than pivot (key) element and the other parts contains all those elements that are greater than pivot element. After that, it again selects a pivot element on each of the sub arrays and repeats the same process until all the elements in the arrays are sorted into an array.
Algorithm of Quick Sort
Partition (A, p, r)
- X <- A[r]
- I <- p-1
- For j <- p to r -1
- Do if A[j] <= x
- Then I <- I + 1
- Exchange A[i] <-> A[j]
- Exchange A[I + 1] <–> A[r]
- Return I + 1
Quicksort (A, p, r)
- While (p < r)
- Do q <- Partition (A, p, r)
- R <- q-1
- While (p < r)
- Do q <- Partition (A, p, r)
- P <- q + 1
Steps to sort an array using the quick sort algorithm
Suppose, we have an array X having the elements X[1], X[2], X[3],…., X[n] that are to be sort. Let’s follow the below steps to sort an array using the quick sort.
Step 1: Set the first element of the array as the pivot or key element. Here, we assume pivot as X[0], left pointer is placed at the first element and the last index of the array element as right.
Step 2: Now we starts the scanning of the array elements from right side index, then
If X[key] is less than X[right] or if X[key] < X[Right],
- Continuously decreases the right end pointer variable until it becomes equal to the key.
- If X[key] > X[right], interchange the position of the key element to the X[right] element.
- Set, key = right and increment the left index by 1.
Step 3: Now we again start the scanning of the element from left side and compare each element with the key element. X[key] > X[left] or X[key] is greater than X[left], then it performs the following actions:
- Continuously compare the left element with the X[key] and increment the left index by 1 until key becomes equal to the left.
- If X[key] < X[left], interchange the position of the X[key] with X[left] and go to step 2.
Step 4: Repeat Step 2 and 3 until the X[left] becomes equal to X[key]. So, we can say that if X[left] = X[key], it shows the termination of the procedures.
Step 5: After that, all the elements at the left side will be smaller than the key element and the rest element of the right side will be larger than the key element. Thus indicating the array needs to partitioned into two sub arrays.
Step 6: Similarly, we need to repeatedly follow the above procedure to the sub arrays until the entire array becomes sorted.
Let’s see an example of quick sort.
Example: Consider an array of 6 elements. Sort the array using the quick sort.
arr[] = {50, 20, 60, 30, 40, 56}
In the above array, 50 is in its right place. So, we divided the elements that are less than pivot in one sub array and the elements that are larger than the pivot element in another sub array.
Hence, we get the sorted array.
Let’s implement the above logic in C program.
Quick.c
Output:
Sorted Array is: Array = 50 20 60 30 40 56
Merge sort
Merge sort is a most important sorting techniques that work on the divide and conquer strategies. It is the most popular sorting techniques used to sort data that is externally available in a file. The merge sort algorithm divides the given array into two halves (N/2). And then, it recursively divides the set of two halves array elements into the single or individual elements or we can say that until no more division can take place. After that, it compares the corresponding element to sort the element and finally, all sub elements are combined to form the final sorted elements.
Steps to sort an array using the Merge sort algorithm
- Suppose we have a given array, then first we need to divide the array into sub array. Each sub array can store 5 elements.
- Here we gave the first sub array name as A1 and divide into next two subarray as B1 and B2.
- Similarly, the right sub array name as A2 and divide it into next two sub array as B3 and B4.
- This process is repeated continuously until the sub array is divided into a single element and no more partitions may be possible.
- After that, compare each element with the corresponding one and then start the process of merging to arrange each element in such a way that they are placed in ascending order.
- The merging process continues until all the elements are merged in ascending order.
Let’s see an example of merge sort.
Example: Consider an array of 9 elements. Sort the array using the merge sort.
arr[] = {70, 80, 40, 50, 60, 11, 35, 85, 2}
Hence, we get the sorted array using the merge sort.
Let’s implement the above logic in a C program.
Merge.c
Output:
Predefined Array is 70 80 40 50 60 11 35 85 2 Sorted array using the Merge Sort algorithm 2 11 35 40 50 60 70 80 85
Quick Sort vs. Merge Sort
S.N. | Parameter | Quick Sort | Merge Sort |
---|---|---|---|
1. | Definition | It is a quick sort algorithm that arranges the given elements into ascending order by comparing and interchanging the position of the elements. | It is a merge sort algorithm that arranges the given sets of elements in ascending order using the divide and conquer technique, and then compare with corresponding elements to sort the array. |
2. | Principle | It works on divide and conquer techniques. | It works on divide and conquer techniques. |
3. | Partition of elements | In quick sort, the array can be divide into any ratio. | Merge sort partition an array into two sub array (N/2). |
4. | Efficiency | It is more efficient and work faster in smaller size array, as compared to the merge sort. | It is more efficient and work faster in larger data sets or array, as compare to the quick sort. |
5 | Sorting method | It is an internal sorting method that sort the array or data available on main memory. | It is an external sorting method that sort the array or data sets available on external file. |
6 | Time complexity | Its worst time complexity is O (n2). | Whereas, it’s worst time complexity is O (n log n). |
7 | Preferred | It is a sorting algorithm that is applicable for large unsorted arrays. | Whereas, the merge sort algorithm that is preferred to sort the linked lists. |
8 | Stability | Quick sort is an unstable sort algorithm. But we can made it stable by using some changes in programming code. | Merge sort is a stable sort algorithm that contains two equal elements with same values in sorted output. |
9 | Requires Space | It does not require any additional space to perform the quick sort. | It requires the additional space as temporary array to merge two sub arrays. |
10. | Functionality | Compare each element with the pivot until all elements are arranged in ascending order. | Whereas, the merge sort splits the array into two parts (N/2) and it continuously divides the array until an element is left. |