What would the expected number of swaps in a merge sort be? [closed]

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite












If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would take place?







share|cite|improve this question












closed as off-topic by Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy Aug 25 at 11:32


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.












  • @Newb Wouldn't that only give an answer up to multiplication by a constant? I think OP wants an exact answer in terms of $n$ ...
    – Zubin Mukerjee
    Apr 18 '15 at 21:27














up vote
2
down vote

favorite












If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would take place?







share|cite|improve this question












closed as off-topic by Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy Aug 25 at 11:32


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.












  • @Newb Wouldn't that only give an answer up to multiplication by a constant? I think OP wants an exact answer in terms of $n$ ...
    – Zubin Mukerjee
    Apr 18 '15 at 21:27












up vote
2
down vote

favorite









up vote
2
down vote

favorite











If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would take place?







share|cite|improve this question












If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would take place?









share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Apr 18 '15 at 21:25









vineel13

134




134




closed as off-topic by Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy Aug 25 at 11:32


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.




closed as off-topic by Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy Aug 25 at 11:32


This question appears to be off-topic. The users who voted to close gave this specific reason:


  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jendrik Stelzner, Xander Henderson, max_zorn, user91500, amWhy
If this question can be reworded to fit the rules in the help center, please edit the question.











  • @Newb Wouldn't that only give an answer up to multiplication by a constant? I think OP wants an exact answer in terms of $n$ ...
    – Zubin Mukerjee
    Apr 18 '15 at 21:27
















  • @Newb Wouldn't that only give an answer up to multiplication by a constant? I think OP wants an exact answer in terms of $n$ ...
    – Zubin Mukerjee
    Apr 18 '15 at 21:27















@Newb Wouldn't that only give an answer up to multiplication by a constant? I think OP wants an exact answer in terms of $n$ ...
– Zubin Mukerjee
Apr 18 '15 at 21:27




@Newb Wouldn't that only give an answer up to multiplication by a constant? I think OP wants an exact answer in terms of $n$ ...
– Zubin Mukerjee
Apr 18 '15 at 21:27










1 Answer
1






active

oldest

votes

















up vote
0
down vote













Let me Google that for you ... http://en.wikipedia.org/wiki/Merge_sort#Analysis






share|cite|improve this answer



























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    0
    down vote













    Let me Google that for you ... http://en.wikipedia.org/wiki/Merge_sort#Analysis






    share|cite|improve this answer
























      up vote
      0
      down vote













      Let me Google that for you ... http://en.wikipedia.org/wiki/Merge_sort#Analysis






      share|cite|improve this answer






















        up vote
        0
        down vote










        up vote
        0
        down vote









        Let me Google that for you ... http://en.wikipedia.org/wiki/Merge_sort#Analysis






        share|cite|improve this answer












        Let me Google that for you ... http://en.wikipedia.org/wiki/Merge_sort#Analysis







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Apr 18 '15 at 22:09









        Greg Martin

        34.1k23060




        34.1k23060












            這個網誌中的熱門文章

            How to combine Bézier curves to a surface?

            Mutual Information Always Non-negative

            Why am i infinitely getting the same tweet with the Twitter Search API?