# Which is better – Merge sort or Quick sort?self.__wrap_b=(t,n,e)=>{e=e||document.querySelector(`[data-br="\${t}"]`);let a=e.parentElement,r=R=>e.style.maxWidth=R+"px";e.style.maxWidth="";let o=a.clientWidth,c=a.clientHeight,i=o/2-.25,l=o+.5,u;if(o){for(;i+1<l;)u=Math.round((i+l)/2),r(u),a.clientHeight===c?l=u:i=u;r(l*n+o*(1-n))}e.__wrap_o||(typeof ResizeObserver!="undefined"?(e.__wrap_o=new ResizeObserver(()=>{self.__wrap_b(0,+e.dataset.brr,e)})).observe(a):process.env.NODE_ENV==="development"&&console.warn("The browser you are using does not support the ResizeObserver API. Please consider add polyfill for this API to avoid potential layout shifts or upgrade your browser. Read more: https://github.com/shuding/react-wrap-balancer#browser-support-information"))};self.__wrap_b(":R4mr36:",1)

Sorting is a process of arranging items systematically. It is very important to deeply understand sorting algorithms as they are frequently asked in technical and coding interviews.

## Different Sorting Algorithms

In this article, we’ll learn the difference between Merge & Quick Sort, which one is more efficient to use, and why.

## What is Merge Sort?

Merge Sort uses the divide and conquer technique. In the divide and conquer technique, we divide the problem into multiple subproblems, solve them individually, and then their results are combined to form a final solution.

Similarly, in Merge Sort, we –

• divide the array into two parts
• get both parts sorted via recursion
• merge the sorted parts

### Working

The height of the Merge Sort tree is O(log n). At each recursive call, we divide in half, sequentially. The overall work done at the nodes of depth ‘i’ is O(n). We partition and merge the 2i sequence of size n/2i.We make 2i+1 recursive calls. Thus, the total running time of merge-sort is O(n*log n).

Time complexity:
Best case – O(n*log n)
Average case – O(n*log n)
Worst case – O(n*log n)

### Implementation

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```import java.util.Arrays;

public class MERGESORTING {
public static void main(String[] args) {
int[] arr={5,4,3,2,1};
merge(arr,0, arr.length);
System.out.println(Arrays.toString(arr));
}
static void merge(int[] arr,int start,int end){
if(end-start==1){
return;
}
int mid=start+(end-start)/2;
merge(arr,start,mid);
merge(arr,mid,end);
mergeSort(arr,start,mid,end);
}
static int[] mergeSort(int[] arr,int start,int mid,int end){
int[] mix=new int[end-start];
int i=start;
int j=mid;
int k=0;
while(i<mid && j<end){
if(arr[i]<arr[j]){
mix[k]=arr[i];
i++;
}
else{
mix[k]=arr[j];
j++;
}
k++;
}
while(i<mid){
mix[k]=arr[i];
i++;
k++;
}
while(j<end){
mix[k]=arr[j];
j++;
k++;
}
for(int l=0;l< mix.length;l++){
arr[start+l]=mix[l];
}
return arr;
}
}```Code language: Java (java)```
``````Ouput:
[1, 2, 3, 4, 5]```Code language: Java (java)```

## What is Quick Sort?

Quick Sort also follows the divide and conquer technique. Quick Sort picks an element as a pivot. Numbers less than the pivot are put on the left-hand side of the pivot and numbers greater than the pivot are put on the right-hand side of the pivot. After every pass, you’re putting the pivot in the correct position.

Choosing the pivot:

• It can be any random element
• You can select the rightmost or leftmost element as a pivot.
• Median can be selected as a pivot

### Working

Here, we are taking the median as the pivot element.

Time complexity:
Worst case – When the pivot is the smallest element all the time, resulting in an unbalanced partition. So, the worst-case complexity is O(n2).
Best case – When the partition is always balanced i.e. pivot is always in the middle. So, the best-case complexity is O(n*log n).
Average case – Quick Sort’s average case time complexity is O(n*log n).

### Implementation

``````import java.util.Arrays;

public class Quick_Sort {
public static void main(String[] args) {
int[] nums={5,4,3,2,1};
sort(nums,0,nums.length-1);
System.out.println(Arrays.toString(nums));
}
static void sort(int[] nums,int low, int high){
if(low>=high){
return;
}
int s=low;
int e=high;
int m=s+(e-s)/2;
int pivot=nums[m];
while(s<=e) {

while (nums[s] < pivot) {
s++;
}
while (nums[e] > pivot) {
e--;
}
if(s<=e){
int temp=nums[s];
nums[s]=nums[e];
nums[e]=temp;
s++;
e--;
}
}
//now my pivot is at correct index, sort the two halves now
sort(nums,low,e);
sort(nums,s,high);
}
}
```Code language: Java (java)```
``````Output:
[1, 2, 3, 4, 5]```Code language: Java (java)```

## Merge Sort or Quick Sort

Now that we’ve learned about Merge and Quick Sort and their differences, it’s time to judge which one is better and why.

Despite the complexity of both algorithms being the same, most people prefer to use Quick Sort. This is because:-

• The locality of reference (reading elements in cache) also plays an important role. Quick Sort employs good cache locality which makes it faster than Merge Sort.
• It is easier to avoid the worst case in Quick Sort by just choosing the appropriate element as a pivot
• Quick Sort is in place i.e. no extra memory is required
• Merge Sort takes more space so it is not recommended to use it on large unsorted arrays. Quick Sort is a better option

However, since Quick Sort is an unstable sorting technique, it may change the occurrence of the two similar elements, whereas, Merge Sort is a stable algorithm and doesn’t change the occurrence of the similar elements. Merge Sort is preferred for Linked Lists as it reads the data sequentially.

## Conclusion

Both algorithms have their advantages and disadvantages. It depends on the type of data you want to sort. I hope you have understood the concept in detail.