Advanced Sorting Techniques — Merge sort and Quick sort

In my previous article, I have discussed What is sorting and simple sorting techniques. In this article, I hope to discuss Advanced sorting techniques.

Sorting simply means rearranging the elements in an array either ascending order or descending order. When advanced sorting techniques are compared with simple sorting techniques, advanced sorting techniques are more efficient. Though the algorithms are a bit complex rather than simple sorting, the steps are less and the intended output can figure out in a short period. Some of the advanced sorting techniques are Merge sorting, Quick sorting, Bucket sorting, Heap sorting, Shell sorting, Redux sorting. But the most commonly used techniques are Merge sorting and Quick sorting. Thus in this article, I will deep dive into those mentioned techniques.

Merge sort

First of all, the unsorted array is divided into two lists. Then the dividing should repeat until the smallest unit or 1 element. Afterward, each element is compared with the adjacent element and merges both elements in the correct order. Rearranging the lists and merging the lists continue until the number of lists becomes 2. Finally, the sorted 2 lists can merge together and we get the sorted array.

Pseudocode

l = Lower bound, u = Upper bound, m = Middle point

MergeSort (A, l, u){
if (l < u){
m = (l + u)/2
MergeSort (A, l, m)
MergeSort (A, m+1, u)
merge (A, l, m, u)
}
  }

Quick sort

Quick sorting is one of the most efficient sorting techniques. In quick sorting, a pivot should be picked from the elements in the unsorted array. Afterward, the unsorted array partitions considering the selected pivot. When partitioning, the smaller elements than the selected pivot are placed before the pivot and larger elements than the selected pivot are placed after the pivot. There are different ways to select a pivot in an array.

• First element as pivot
• Last element as pivot
• Random element as pivot
• Median as pivot

Pseudocode

l = Lower bound, u = Upper bound, p= Pivot Location

QuickSort(A, l, u){
if(l < u){
p = Partition(A, l, u)
QuickSort(A, l, p-1)
QuickSort(A, p+1, u)
}
  }

This is the end of the article and I hope this would be helpful to you all to understand the Quick sort and Merge sort in a simpler way.

Thank you!!!