Skip to main content
Software Engineering

Return to Question

deleted 23 characters in body
Source Link
digoalbuq2
digoalbuq2
  • 21
  • 4

A question about merge sort... ItMerge Sort contains basically two important routines:

(i) split (ii) merge.

I get the general idea. But I dont understand how this is more efficient than some random bad sort algorithm, like selection sort, for example. I kind understand the maths behind, I know why one is O(n*lg(n)) and the other is O(n²). I know lg32 is 5, and the tree is going to have 5 levels. But in practical terms I don't see the difference. Ok... let me explain how my mind is weirdly thinking.

Let's say we have an array with 32 numbers. Using merge sort, we have to use the split routine 31 times.

(32 -> 16) (1x)

(16-> 8) (2x - split 2 arrays of 16 elements into 4 arrays of 8 elements)

(8-> 4) (4x - split 4 arrays of 8 elements into 8 arrays of 4 elements)

(4 -> 2) (8x)

(2 -> 1) (16x)

Total: 31 splits. Then, we should use the merge routine which is O(n). So, in the end,it's basically 31* n (31 splits multiplied by n - which is the merge routine cost) , so thinking about the total cost of the algorithm is almost n*n...

The only advantage that I see with merge sort is that it can be easily parallelized, there is a huge time efficiency there. But in terms of overall work, I don't see much difference. If parallelization was not allowed, merge sort would still perform better than selection sort for large datasets?

A question about merge sort... It contains basically two important routines:

(i) split (ii) merge.

I get the general idea. But I dont understand how this is more efficient than some random bad sort algorithm, like selection sort, for example. I kind understand the maths behind, I know why one is O(n*lg(n)) and the other is O(n²). I know lg32 is 5, and the tree is going to have 5 levels. But in practical terms I don't see the difference. Ok... let me explain how my mind is weirdly thinking.

Let's say we have an array with 32 numbers. Using merge sort, we have to use the split routine 31 times.

(32 -> 16) (1x)

(16-> 8) (2x - split 2 arrays of 16 elements into 4 arrays of 8 elements)

(8-> 4) (4x - split 4 arrays of 8 elements into 8 arrays of 4 elements)

(4 -> 2) (8x)

(2 -> 1) (16x)

Total: 31 splits. Then, we should use the merge routine which is O(n). So, in the end,it's basically 31* n (31 splits multiplied by n - which is the merge routine cost) , so thinking about the total cost of the algorithm is almost n*n...

The only advantage that I see with merge sort is that it can be easily parallelized, there is a huge time efficiency there. But in terms of overall work, I don't see much difference. If parallelization was not allowed, merge sort would still perform better than selection sort for large datasets?

Merge Sort contains basically two important routines:

(i) split (ii) merge.

I get the general idea. But I dont understand how this is more efficient than some random bad sort algorithm, like selection sort, for example. I kind understand the maths behind, I know why one is O(n*lg(n)) and the other is O(n²). I know lg32 is 5, and the tree is going to have 5 levels. But in practical terms I don't see the difference. Ok... let me explain how my mind is weirdly thinking.

Let's say we have an array with 32 numbers. Using merge sort, we have to use the split routine 31 times.

(32 -> 16) (1x)

(16-> 8) (2x - split 2 arrays of 16 elements into 4 arrays of 8 elements)

(8-> 4) (4x - split 4 arrays of 8 elements into 8 arrays of 4 elements)

(4 -> 2) (8x)

(2 -> 1) (16x)

Total: 31 splits. Then, we should use the merge routine which is O(n). So, in the end,it's basically 31* n (31 splits multiplied by n - which is the merge routine cost) , so thinking about the total cost of the algorithm is almost n*n...

The only advantage that I see with merge sort is that it can be easily parallelized, there is a huge time efficiency there. But in terms of overall work, I don't see much difference. If parallelization was not allowed, merge sort would still perform better than selection sort for large datasets?

Source Link
digoalbuq2
digoalbuq2
  • 21
  • 4

Merge Sort Concept Understanding

A question about merge sort... It contains basically two important routines:

(i) split (ii) merge.

I get the general idea. But I dont understand how this is more efficient than some random bad sort algorithm, like selection sort, for example. I kind understand the maths behind, I know why one is O(n*lg(n)) and the other is O(n²). I know lg32 is 5, and the tree is going to have 5 levels. But in practical terms I don't see the difference. Ok... let me explain how my mind is weirdly thinking.

Let's say we have an array with 32 numbers. Using merge sort, we have to use the split routine 31 times.

(32 -> 16) (1x)

(16-> 8) (2x - split 2 arrays of 16 elements into 4 arrays of 8 elements)

(8-> 4) (4x - split 4 arrays of 8 elements into 8 arrays of 4 elements)

(4 -> 2) (8x)

(2 -> 1) (16x)

Total: 31 splits. Then, we should use the merge routine which is O(n). So, in the end,it's basically 31* n (31 splits multiplied by n - which is the merge routine cost) , so thinking about the total cost of the algorithm is almost n*n...

The only advantage that I see with merge sort is that it can be easily parallelized, there is a huge time efficiency there. But in terms of overall work, I don't see much difference. If parallelization was not allowed, merge sort would still perform better than selection sort for large datasets?