Interview Preparation Merge Sort - Revision history

Proj user18 at 11:02, 1 December 2016

2016-12-01T11:02:08Z

Proj user18 at 13:18, 25 November 2016

2016-11-25T13:18:36Z

Proj user18 at 13:18, 25 November 2016

2016-11-25T13:18:00Z

Proj user18 at 12:35, 25 November 2016

2016-11-25T12:35:36Z

Proj user18 at 12:34, 25 November 2016

2016-11-25T12:34:52Z

Proj user18 at 12:33, 25 November 2016

2016-11-25T12:33:25Z

Proj user18 at 12:32, 25 November 2016

2016-11-25T12:32:56Z

Proj user18 at 12:31, 25 November 2016

2016-11-25T12:31:34Z

Proj user18: 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..."

2016-11-25T12:25:07Z

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..."

New page

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 smaller index number is greater than element at higer index than shift the element at smaller index towards right.

d. Store element of higher value in the last index where vacancy is created.

e. Repeating step b, c and d until the array is sorted.

For an array with n number of elements,

Best case complexity = O(n).

Average case complexity = Worst case complexity = O(n^2).

@@ Line 22: / Line 22: @@
+     {
        temp[k] = a[i];
+     }
      else
+     {
        temp[k] = a[j];
+     }
+   }
@@ Line 31: / Line 35: @@
+   {
      temp[k] = a[i];
+   }
    while(j<= end)
+   {
      temp[k] = a[j];
+   }
    for(i = start ; i < k ; i++)

@@ Line 45: / Line 45: @@
 void SORT::mergesort(int *a, int start, int end)
+{
    if (start < end)
+   {
@@ Line 53: / Line 52: @@
      SORT::merge(a,start, mid, end);
+   }
 }</pre>

← Older revision		Revision as of 13:18, 25 November 2016
Line 12:		Line 12:

	d. Store all the elements in the temporary buffer back the main array.		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];
		+	}
		+	else
		+	{
		+	temp[k] = a[j];
		+	}
		+	}
		+	while(i<= mid)
		+	{
		+	temp[k] = a[i];
		+	}
		+	while(j<= end)
		+	{
		+	temp[k] = a[j];
		+	}
		+	for(i = start ; i < k ; i++)
		+	{
		+	a[i] = temp[i];
		+	}
		+	}</pre>
		+
		+	<pre>
		+	void SORT::mergesort(int *a, int start, int end)
		+	{
		+	int mid;
		+	if (start < end)
		+	{
		+	mid = ( (start+end) / 2 );
		+	SORT::mergesort(a,start, mid);
		+	SORT::mergesort(a, mid+1, end);
		+	SORT::merge(a,start, mid, end);
		+	}
		+	return;
		+	}</pre>

	For an array with n number of elements,		For an array with n number of elements,

@@ Line 5: / Line 5: @@
 b. Starting from leaf node traverse the same route backward:
-	* Compare the last two nodes.
+*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.
+*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.

@@ Line 5: / Line 5: @@
 b. Starting from leaf node traverse the same route backward:
-	b.1. Compare the last two nodes.
+	* Compare the last two nodes.
-	b.2. 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 temporary buffer.
+	* 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 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.

@@ 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.
+c. Repeat step b until all the elements are copied to temporary buffer.
-d. Store element of higher value in the last index where vacancy is created.
+d. Store all the elements in the temporary buffer back the main array.
 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-