What are the advantages and disadvantages of merge sort?

Answer 1

Insertion sort provides several advantages:

Simple implementation.

Efficient for (quite) small data sets.

Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions.

More efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n).

Stable, i.e. does not change the relative order of elements with equal keys

In-place, i.e. only requires a constant amount O(1) of additional memory space

Online, i.e. can sort a list as it receives it.

Disadvantages of insertion sort;

It is less efficient on list containing more number of elements.

As the number of elements increases the performance of the program would be slow.

Insertion sort needs a large number of element shifts.

Answer 2

The advantages to merge sort is it is always fast. Even in its worst case its runtime is O(nlogn). It is also stable. Disadvantages of Merge sort are that it is not in place so merge sort uses a lot of memory. It uses extra space proportional to n. This can slow it down when attempting to sort very large data.

Answer 3

• It can be applied to files of any size.

• Reading of the input during the run-creation step is sequential ==> Not much seeking.

• Reading through each run during merging and writing the sorted record is also sequential. The only seeking necessary is as we switch from run to run.

• If heapsort is used for the in-memory part of the merge, its operation can be overlapped with I/O

• Since I/O is largely sequential, tapes can be used.

Answer 4

A bubble sort is a sort where adjacent items in the array or list are scanned repeatedly, swapping as necessary, until one full scan performs no swaps.

Advantage is simplicity.

Disadvantage is that it can take N scans, where N is the size of the array or list, because an out of position item is only moved one position per scan. This can be mitigated somewhat by starting with a swap gap of greater than one (typically N/2), scanning until no swaps occur, then halving the gap and repeating until the gap is one. This, of course, is no longer a bubble sort - it is a merge exchange sort.

Answer 5

Interchange sort is better known as selection sort. The disadvantages are that it is not a stable sort (equal values may not be in the same order they were input) and that it has a best, worst and average time complexity of O(n^2). Even a bubble sort has a best case of O(n) and is a stable sort, but bubble sort is a classic example of how not to write an algorithm! Any sorting algorithm that performs worse than bubble sort has no advantages other than as a purely academic exercise. It has no practical application whatsoever.

To understand why selection sort is so abysmal, you need to examine the algorithm:

Given a set of n elements, locate the smallest element and swap with the first element. That element is now the last element of the sorted set and the unsorted set is thus reduced by 1 element. Repeat for the remaining n-1 unsorted elements (for all n>1).

The first iteration of the algorithm takes O(n) time because it requires n-1 comparisons to determine the smallest element in an unsorted set plus 1 swap operation to put it in place (we ignore the time difference between a comparison and a swap). The next iteration finds the next smallest element and that requires O(n-1) time. Even if the set were already sorted to begin with we've already performed nearly twice the number of comparisons required by a bubble sort. This is because a bubble sort traverses the set in pairs and only swaps pairs if they are in the wrong order. If no swaps occur during an iteration, then the unsorted set is already sorted, hence it has a best case of O(n).

Answer 6

The obvious advantage of shell sort is that it can handle larger data sets more efficiently than insertion sort. However, that efficiency comes at the cost of stability and, for small data sets, insertion sort will generally perform better. Shell sort has no real-world applications because if we are willing to sacrifice stability purely to handle larger data sets then we might as well use intro sort instead (a quicksort that degrades to heap sort). Stable sorts are typically implemented using merge sort or Timsort (a variation of merge sort that degrades to insertion sort).

Stability relates to how we compare equal values. With a stable sort, equal values remain in the same order they were input but with unstable sorts we cannot guarantee this. You might well ask why this matters. After all, if two values are equal does it really matter which value comes first? For simple values where the value is the one and only key, the answer is no; the order does not matter. However, if a value has two or more keys and we wish to sort by any of those keys, the input order matters. A lot!

Consider a list of files. We can sort files by name, type, size, date, or indeed by any file attribute we choose. However, if we sort files by name and then sort by type, we would rightly expect files of the same type to remain in name order. A stable sort guarantees this because the secondary key is automatically implied by the input order, the order that was generated when we sorted by name. We do not have to consider the secondary key (whatever it may be) because equal primary keys remain in the order they were input. An unstable sort cannot guarantee this unless we keep track of the input order and use that as a secondary key to compare equal primary keys, and that increases the complexity of the comparison algorithm (never mind the fact we also have to keep track of which keys are secondary, tertiary, and so on).

Answer 7

Selection sort is ideally suited to sorting small sets and, since it does not require random access, can be adapted to sort both lists and arrays. However, insert sort generally performs better when sorting arrays.

To understand the disadvantage, you need to compare the algorithms. Selection sort starts by treating the entire set as the unsorted set. It then assumes the first element is the largest element and begins comparing all other elements to this element. When it finds a larger or equal element, the remaining elements are compared to this element. Once all elements have been compared, the largest element will have been located. This is then swapped with the last element. The last element then becomes the first element of the sorted set and the unsorted set is reduced by one element. The algorithm repeats until there is only one element in the unsorted set, at which point the entire set is sorted. That one element is always the smallest element because everything in the sorted set is either larger or equal to it, thus it is already in place.

Thus for a set of n elements, there are n-1 iterations. Each iteration requires n-1 comparison operations (where n reduces by one at the end of each iteration) and 1 swap operation.

With insert sort we build the sorted set at the beginning of the set rather than the end. A set of one can always be regarded as being sorted, thus we begin with a sorted set of 1 and an unsorted set of n-1 elements. We then copy the first element from the unsorted set, thus creating a gap between the sorted and unsorted sets. If the element to the left of that gap is larger than the copied element, we move that element into the gap, one position to the right, which subsequently moves the gap one position to the left. If the gap reaches the beginning of the sorted set or the element to its left is not larger than the copied element, then we place the copied element in the gap. We then repeat the process for the next unsorted element until there are no more unsorted elements.

Thus there are n-1 iterations (same as for selection sort) and at least two copies per iteration (one to move the element out of the unsorted set, and another to move it back into the sorted set). On each iteration, a sorted set of k elements will require 1 to k comparison operations and a similar number of move operations. Since we stop comparing when we have found the insertion point, we will generally perform fewer comparisons overall than selection sort unless the unsorted set happens to be in reverse order. However, we will incur more move operations depending on where the insertion point lands on each iteration (bearing in mind that a swap is equivalent to 3 move operations).

Thus for a set of 10 elements, selection sort will perform 9 iterations, with 9+8+7+6+5+4+3+2+1=45 comparisons and 2x9=18 swaps (equivalent to 54 move operations), thus we have 99 operations in total.

Insert sort would also require 9 iterations, however the number of comparisons and moves will vary. In the best case, where the set is already sorted, there will be a minimum of 9 comparisons and 18 moves (27 operations in total) and in the worst case, where the set is in reverse order, there will be 45 comparisons and 3+4+5+6+7+8+9+10+11=63 moves, thus we have 108 operations in total.

While there will inevitably be some cases where selection sort outperforms an insert sort, in the vast majority of cases insert sort will be substantially quicker than selection sort, because selection sort will always take 99 operations to sort a set of 10 elements, whereas insert sort will take anything from 27 to 108 operations, with an average case of 68 operations.

Selection sort can be improved slightly by testing the position of the largest element. If it is already the final element of the unsorted set, then we do not need to swap, however this adds an extra comparison to each iteration whether we swap or not. Thus the best case, where the set is already sorted, becomes 54 comparisons with no swaps, and the worst case becomes 54 comparisons with 18 swaps, giving a range of 54 to 108 operations with an average of 81 operations. While this will increase the number of cases where a selection sort outperforms insert sort, selection sort still comes off worst overall.

Answer 8

This algorithm has several advantages. It is simple to write, easy to understand and it only takes a few lines of code. The data is sorted in place so there is little memory overhead and, once sorted, the data is in memory, ready for processing. The major disadvantage is the amount of time it takes to sort.

To learn more about data science please visit- Learnbay.co

Answer 9

what are advantages or disadvantages of bubble sort , quick sort or merge sort

Answer 10

advantages of binary heap