0

Merge Sort

If you are given 4 red sticks of different heights placed from lower to higher height order and 4 green sticks of different heights placed from lower to higher height order. Task is to arrange red and green sticks together from lower to higher height..

A basic way to do this is to pick smallest by comparing smaller sticks of red and green  and place it. Next pick 2nd  highest stick. Continue this till all sticks are placed in correct order. In Merge sort this basic technique of merging to sorted array is used.

MergeExample

Logic:

Merge sort uses a concept of ‘divide and conquer‘ to sort elements.

a.  Divide given elements in half, continue dividing elements unless there is only one element present to sort. As one element is always a sorted element, return and start next step.

b. Merge two elements together in a sorted order. continue merging two sorted sub arrays till all input elements are in sorted order.

Example:

Consider input elements as 4,2,8,1,6,3

MergeSort

Dividing action is performed by calling MergeSort function recursively, in each call mid of  array is calculated and two subarrays are formed like input[start to mid] and input[mid+1 to end] and sorting and merging two subarrays is performed by calling Merge function recursively.

 

Implementation:

 

Analysis:

Calculating mid of array takes  constant time regardless of size of the array . So time complexity of this operation is O(1).

When we combine two sorted array , each element is checked so time complexity for this operation is O(n)

In each step array is divided in half and sort two subarrays of size n/2. So the total time complexity of  sorting n elements can be expressed as following :

T(n) = T(n/2) + T(n/2) + O(n)    :: T(n)=2T(n/2) + O(n)

By using Master theorem, Time complexity is O(nlog n)

Merge sort uses an extra space to hold two halves so his sort is not a in place sort and space complexity is O(n).

0

Bubble Sort

Lets discuss Bubble Sort today.

Problem : Given  a list of integers in random order, arrange them in either ascending or descending order.

For example consider this list of integers : 4 2 8 1 6 then output should be 1 2 4 6 8 or 8 6 4 2 1 .

There are many sorting algorithms which we can use to solve above problem. But lets start with basic simple and easiest algorithm of sorting i.e. Bubble Sort.

Logic

In Bubble sort for ascending order,as the name suggests we will bubble out the largest number to last position (i.e its correct position in sorted array) in the array. And after that we will repeat the same procedure for the rest of the array until all the numbers are at their correct position.

So how do we bubble out largest number ?

We compare adjacent elements with each other and if the number on left side is greater than the number of right side we swap them. So at the end we have the largest number at the end.

Lets take an example :

Bubble sort small

 

 

Implementation: To sort numbers in ascending order

Analysis: 

In this sort, on every pass we will bubble out the largest element from the array to its correct position (i.e. last) this takes O(n) time and we repeat this for every element in array.

After we shift the first largest element to its correct position we reduce the array size by 1.

So, to place 1st element at it’s correct position , number of operations required is : n-1

to place 2nd element at it’s correct position, number of operations required is: n-2  and so on…

So, to sort ‘n’ elements total number of operations required are :  (n-1) + (n-2) + (n-3) + …+1 , which is  n(n+1)/2.  After  ignoring  constants , result is n2. Therefore time complexity of bubble sort in  O(n2). Also the number of swaps in bubble sort will be n2 in worst case !

Highlights:

-Bubble out the largest element to end by swapping adjacent elements

-Time Complexity O(n2).

-Space Complexity O(1) or constant.

-Number of swaps in worst case is n2

-Bubble sort is Stable sort i.e. it maintains the relative order of elements.