Sorting logged!

Hello Geeks! In the previous post we had discussed the three basic sorting techniques: bubble sort, selection sort and insertion sort. In today’s post we shall discuss two much more efficient sorting techniques: “Merge sort” and “Quick sort”. So lets get started!

Merge Sort

Merge sort is a simple divide-and-conquer algorithm, which involves breaking down the array until each sub list consists of only one element of the original array. Now, merging of such sub lists becomes very trivial.  Each sub list is merged such that, the combined list is in sorted order.

This is the most popular example of divide-and conquer algorithm, about which we discussed in the earlier post.

Algorithm (MergeSort)

1. Start
2. If start< end
   1. mid=(start+end)/2
   1. merge_sort(array, start, mid)
   1. merge_sort(array,mid+1, end)
   1. merge (array, start,mid, end)
3. End

Algorithm (Merge)

 void merge(int array[ ] , int start, int mid, int end) {
1. Store int x = start , z = mid+1, k=0

2. for i = start till i <= end do

    2.1 if( array[x] < array[z])   
        2.1.1 array[k] = array[x]
        2.1.2 k++ and x++

    2.2 else if( array[x] > array[z]) 
       2.2.1 array[k] = array[z]
       2.2.2 k++ and z++

    2.3 if(x > mid)    
       2.3.1 array[k] = array[z]
       2.3.2 k++ and z++  

    2.4 else if ( z > end)
        2.4.1 array[k] = array[x]
        2.4.2 k++ and x++

    2.5 i++
 
 3. for  x=0 till  x< k
    3.1 array[ start++ ] = array[ x ] 
    3.2 x++                       
  

Explanation

Let the array have indexes from start to end. And let mid be the central or middle index. So now the array [start to end] can be divided into array [start to mid] and array.

Once divided into two halves, the halves are sorted individually. Then they are combined into one sorted array.

In the divide step, the array or its part is divided into two equal parts. In conqour, the two sub arrays are sorted. And in the combine step, both these are merged such that its combination gives a sorted array. Merge sort uses recursion, meaning, the function calling itself.

Let us understand with an example:

Now how is merging actually done? Watch this!

Use

Many search engines use merge sort, to compare data fetched from other websites.

Time and space complexity

Worst-case-performance	O(N log(N))
Best-case-performance	O(N log(N))
Average-case-performance	O(N log(N))
Worst-case-space complexity	O(N)

Advantages

1. Has one of the best time complexity
2. Well suited for a large collection of data

Disadvantages

1.Takes up more space in memory for the sub lists

---

Quick sort

Quick sort is a divide and conquer algorithm, in which an array is divided into parts based on a pivot element and later merged in a sorted manner.

A pivot element is chosen, based on which the array will be divided. The pivot may be the first element, the last element, middle element or any other suitable, element, as per choice.

All elements of the array are compared to the pivot and the position of the pivot element is determined.

The array thus splits into two parts: One containing all elements lesser than the pivot and the Second containing all elements greater then the pivot element.

The above procedure is applied to both the arrays and consequently to all the sub-arrays formed, until each array contains 1 element. Now, the sub-arrays are clubbed together thus forming the sorted array.

QuickSort algorithm

If beg< end do the following steps

1. Partition the array based on chosen pivot element. (Algorithm given below)
2. Apply quicksort on left subarray as quicksort(a, beg, p-1)
3. Apply quicksort on right subarray as quicksort(a, p+1, end)

Partitioning algorithm

1. Choose the pivot element (here, last element).
2. Take i and j pointing to the beginning and end of the array to be sorted.
3. While a[i]< pivot, increment i.
4. While a[j]>=pivot, decrement j.
5. If 5 is false and 6 is false, swap a[i] and a[j].
6. If j becomes less than i, swap j with pivot, and return.

Let us understand with an example.

Explanation

The first image explains the partitioning of an array into sub-arrays.

‘i’ is incremented and ‘j’ is decremented while a[i] is lesser than pivot and a[j] is greater than the pivot element. Else, i and j are swapped. When all elements are analysed and j becomes less then i, the array is partitioned into 2 subarrays (having unequal length).

Quick sort algorithm is applied on both these subarrays recursively, thus first dividing them (based on the partitioning algorithm) into subarrays of length 1, and finally merging them in sorted order.

The second image depicts the quicksort algorithm, i.e. division and sorting then merging(conquering) of the subarrays.

Time Complexity Analysis

Worst-case-performance	O(N2)
Best-case-performance	O(N log(N))
Average-case-performance	O(N log(N))
Worst-case-space complexity	O(log(N))

Advantages

1. Quick sort is an internal sorting, no auxiliary space is needed for sorting
2. Well suited for smaller collection of data
3. It is one of the fastest sorting algorithms.

Disadvantages

1. Does not work well for large datasets.
2. Time complexity increases significantly for larger number of comparisons.
3. It can be unstable.

Uses

Generally used in commercial applications.

Comparison of Merge and Quick sort

Both merge sort and quick sort are based on the Divide-Conquer-Combine method, about which we had discussed in the previous post.

The main difference, if you observe closely, is that in the Divide step, Merge sort divides the list into two equal sub lists. On the other hand, Quick sort does not guarantee that the division will be equal. It is completely based on the pivot at that point.

In quick sort, sorting is done internally, whereas in merge sort, sorting is done separatly/ externally, using auxiliary memory space.

Do try to analyse the time complexities for the various sorting algorithms. And don’t forget to apply them in your everyday life!

We will be discussing some more interesting sorting techniques in the next post, so stay tuned!

For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com, or comment below.

Don’t forget to Like, Comment and Share with your friends.

Stay Tuned for Everything Geeky.

See you next week!

Cheers!

Team Bitxorbytes

Follow us on instagram:  @bitxorbytes

Cover Image credits: https://www.coindesk.com/hyperledger-on-the-verge-of-merging-blockchain-code-from-ibm-digital-asset