Python Merge Sort

Here you may study python merge kind formula.

Merge kind relies on divide and conquer technique.

All we’ve to try to do is divide our array into a pair of components or sub-arrays and people sub-arrays are divided into alternative two equal parts.

we are going to divide the array during this manner till we tend to get a single component in every part as a result of a single element is already sorted.

After dividing the array into numerous sub-arrays having single component, currently, it’s the time to overcome or merge them along however in a sorted manner.

Python Merge kind

Example

Let’s see Associate in Nursing example:

We have Associate in Nursing array [ ninety nine, 21, 19, 22, 28, 11, 14, 18 ].

Python Merge kind one

There are eight parts within the array. Break it into 2 equal components.

Python Merge kind a pair of

And repeat breaking till we tend to get a single component in every part or sub-array.

Python Merge kind 3

Python Merge kind four

We have a single component in every sub-array. currently we’ve to merge them within the same method as had divided it, however in a sorted manner.

Compare ninety-nine with twenty-one, 19 with 22, 28 with 11, fourteen with eighteen and place the smaller range 1st (for ascending order).

Python Merge kind five

here we’ve sorted arrays, keep capture till we tend to get a complete sorted array.

Python Merge kind six

And finally, our array is sorted.

Python Merge kind seven

This was the theoretical construct, currently, take a glance on the way to implement this idea in programming.

First, we’ll see Associate in Nursing formula, within which we’ll divide given array into sub-arrays exploitation formula.

Second, we’ll see the formula for merging 2 sub-arrays into one array however in sorted order.

Algorithm

Mergesort(Array)

Step:1-

set n = length(Array)

If (n<2) so return

Step:2- set middle = n/2

Initialize array “left” having size (mid)

Initialize array “right” having size (n-mid)

Step:3- for i = zero to middle – one

left [i] = Array[i]

right[i] = Array[i]

Step:4- decision mergesort(left)

Call mergesort(right)

Call merge(left,right,Array)

merge(left, right, Array)

Step:1 – set i = zero, j =0, k = 0

Step:2 –   while (i<length(left) and j<length(right)

{

If (left[i] < right[j])

Then set Array[k] = left[i]

Increase i by 1

[end of if statement]

else

Set Array[k] = right[j]

Increase j  by 1

[end of else statement]

Increase  k by 1

[end of while loop]

Step:3- while (i < length(left))

{

Set Array[k] = left[i]

i = i + 1

k = k + 1

}

While (j < length(right))

{

Array[k] = Right[j]

Increase j by 1

Increase k by 1

}

Code

Array = [99,21,19,22,28,11,14,18]
 
#function for merging two sub-arrays
def merge(left, right, Array):
  i = 0
  j = 0
  k = 0
 
  while (i<len(left) and j<len(right)):
    if(left[i]<right[j]):
      Array[k] = left[i]
      i = i+1
    else:
      Array[k] = right[j]
      j = j+1
 
    k = k+1
  
  while(i<len(left)):
    Array[k] = left[i]
    i = i+1
    k = k+1
  
  while(j<len(right)):
    Array[k] = right[j]
    j = j+1
    k = k+1
 
#function for dividing and calling merge function
def mergesort(Array):
  n = len(Array)
  if(n<2):
    return
 
  mid = n/2
  left = []
  right = []
  
  for i in range(mid):
    number = Array[i]
    left.append(number)  
   
  for i in range(mid,n):
    number = Array[i]
    right.append(number)
 
  mergesort(left)
  mergesort(right)
 
  merge(left,right,Array)
 
#calling mergesort
mergesort(Array)
for i in Array:
  print i,

Output

11 14 18 19 21 22 28 99

Comment Down If you Have any Doughts.