2,020 views
1 votes
1 votes

why not merge sort?we don’t swap in merge sort,we just create auxillary arrays and merge them by changing elements in the original array.should we consider that as a swap?

5 Answers

1 votes
1 votes

For number of swaps in merge sort, see the pictures below. Recursive merge sort is used.

0 votes
0 votes
Just think about for 2 element array .and apply the merge sort .You can clearly see that there is a sawp between the 2 elements.

So yes merge sort also performs swap between elements .

No of swap in merge sort =O(N^2)
0 votes
0 votes
In selection sort the number of swaps is always O(n).

Why? We find minimum element in unsorted part of array and swap it with first element of unsorted part of array. So for each phase only 1 swap is there.

In Insertion Sort in worst case number of swaps is O($n^2$). For merge sort no of swap is $O(N^2)$
edited by
0 votes
0 votes

Firstly, they have not asked about the number of comparisons. They are asking about the swaps that will take place in sortings-

  1. In quick sort total 0(n^2) swaps take place. i.e initially we have to find element from LHS to R.H.S. which is greater than pivot and then from R.H.S. to L.H.S. for element smaller than pivot. If found then swap and repeat and divide and repeat. 
  2.  In selection sort find the minimum element and then swap with first element. Repeat and swap. Thus 0(n) swaps.
  3. In merge sort first n/2 then n/2 then n/2…… total 0(nlogn) swaps
  4. in bubble sort  0(n^2)  swaps take place.

Hence option B is correct

edited by

Related questions

0 votes
0 votes
0 answers
3
Abhishek Kumar 38 asked Dec 19, 2018
611 views
Which of the following sorting algorithm represented by above code?