CODEWITHSUNDEEP
algorithmmergesort
MrCoder
MrCoder

Reputation: 103

Is merge sort an adaptive algorithm?

We have 3 variants of Merge sort.

  1. Top down
  2. Bottom up
  3. Natural

Are any of these adaptive algorithms? For instance, if an array is sorted they will take advantage of the sorted order.

According to me, no matter if an array is sorted or not, merge sort will still go in for comparisons and then merge. So, the answer is none of these are adaptive.

Is my understanding is correct?

Upvotes: 1

Views: 4015

Answers (3)

user3621123
user3621123

Reputation:

Accoring to me, no matter if an array is sorted or not, merge sort will still go in for comparisons

I don't think its possible to sort without any comparisons and save memory if the input is not already sorted or contains information regarding what sorting procidure to follow. The fastest sorting algorithm is of time complexity O(n log(n)) (there are sorting techniques like bead sorting. I am not considering it here as it is not an optimal method memory vice)

P.S quick sort does involve comparisons (but is adaptive), and in its worse case it makes about O(n^2) comparisons.

P.P.S Radix sort, counting sort and bucket sort are some examples of adaptive sort;

Upvotes: 0

MBo
MBo

Reputation: 80287

Natural merge sort is adaptive. For example, it executes only one run through sorted array and makes N comparisons.

Both top down and bottom up sorts are not adaptive, they always make O(NlogN) operations

Upvotes: 2

Md Johirul Islam
Md Johirul Islam

Reputation: 874

Merge Sort is an implementation of divide and conquer algorithm. You need to divide the whole array into sub arrays. For example [1, 3 ,5, 6, 2, 4,1 10] is divided into [1 3 5 6] and [2 4 1 10]. [1 3 5 6] is divided into [1 3] and [5 6]. Now as both [1 3] and [5 6] are sorted swap procedure is not needed.

So there is at least a little complexity if the array is sorted

Upvotes: 0

Related Questions