Difference between revisions of "Interview Preparation Merge Sort"

From Embedded Systems Learning Academy
Jump to: navigation, search
(Created page with "Algorithm for implementation of insertion sort is as follows a. Start from index 1. b. compare higher index element with all the elements at smaller index. c. If element at...")
 
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Algorithm for implementation of insertion sort is as follows
+
Algorithm for implementation of merge sort is as follows
  
−
a. Start from index 1.
+
a. Divide the string into two half using formula (start index + end index)/2, where each half have a new start and end index till one element is left in the leaf node.
  
−
b. compare higher index element with all the elements at smaller index.
+
b. Starting from leaf node traverse the same route backward:
  
−
c. If element at smaller index number is greater than element at higer index than shift the element at smaller index towards right.
+
*Compare the last two nodes.
  
−
d. Store element of higher value in the last index where vacancy is created.
+
*Traverse each node whichever element in the node is smaller save the element in the temporary buffer first then save the element of the other node at incremented index in the temporary buffer.
  
−
e. Repeating step b, c and d until the array is sorted.
+
c. Repeat step b until all the elements are copied to the temporary buffer.
 +
 
 +
d. Store all the elements in the temporary buffer back the main array.
 +
 
 +
'''Pseudo Code'''
 +
<pre>
 +
void SORT::merge(int *a, int start, int mid, int end)
 +
{
 +
  while(i <= mid && j <= end)
 +
  {
 +
    if(a[i] < a[j])
 +
    {
 +
      temp[k] = a[i];
 +
      i++;
 +
      k++;
 +
    }
 +
    else
 +
    {
 +
      temp[k] = a[j];
 +
      j++;
 +
      k++;
 +
    }
 +
  }
 +
  while(i<= mid)
 +
  {
 +
    temp[k] = a[i];
 +
    i++;
 +
    k++;
 +
  }
 +
  while(j<= end)
 +
  {
 +
    temp[k] = a[j];
 +
    j++;
 +
    k++;
 +
  }
 +
  for(i = start ; i < k ; i++)
 +
  {
 +
    a[i] = temp[i];
 +
  }
 +
}</pre>
 +
 
 +
<pre>
 +
void SORT::mergesort(int *a, int start, int end)
 +
{
 +
  if (start < end)
 +
  {
 +
    mid = ( (start+end) / 2 );
 +
    SORT::mergesort(a,start, mid);
 +
    SORT::mergesort(a, mid+1, end);
 +
    SORT::merge(a,start, mid, end);
 +
  }
 +
}</pre>
  
 
For an array with n number of elements,
 
For an array with n number of elements,
  
−
Best case complexity = O(n).  
+
Best case complexity = Average case complexity = Worst case complexity = O(n log n).
  
−
Average case complexity = Worst case complexity = O(n^2).
+
For an animated model refer to following URL http://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-

Latest revision as of 11:02, 1 December 2016

Algorithm for implementation of merge sort is as follows

a. Divide the string into two half using formula (start index + end index)/2, where each half have a new start and end index till one element is left in the leaf node.

b. Starting from leaf node traverse the same route backward:

  • Compare the last two nodes.
  • Traverse each node whichever element in the node is smaller save the element in the temporary buffer first then save the element of the other node at incremented index in the temporary buffer.

c. Repeat step b until all the elements are copied to the temporary buffer.

d. Store all the elements in the temporary buffer back the main array.

Pseudo Code 

void SORT::merge(int *a, int start, int mid, int end)
{
  while(i <= mid && j <= end)
  {
    if(a[i] < a[j])
    {
      temp[k] = a[i];
      i++;
      k++;
    }
    else
    {
      temp[k] = a[j];
      j++;
      k++;
    }
  }
  while(i<= mid)
  {
    temp[k] = a[i];
    i++;
    k++;
  }
  while(j<= end)
  {
    temp[k] = a[j];
    j++;
    k++;
  }
  for(i = start ; i < k ; i++)
  {
    a[i] = temp[i];
  }
}
void SORT::mergesort(int *a, int start, int end)
{
  if (start < end)
  {
    mid = ( (start+end) / 2 );
    SORT::mergesort(a,start, mid);
    SORT::mergesort(a, mid+1, end);
    SORT::merge(a,start, mid, end);
  }
}

For an array with n number of elements,

Best case complexity = Average case complexity = Worst case complexity = O(n log n).

For an animated model refer to following URL http://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-

Retrieved from "http://socialledge.com/sjsu/index.php?title=Interview_Preparation_Merge_Sort&oldid=29717"