Data Structures and Algorithms Discussion Board
September 10, 2010, 02:40:53 PM *
Welcome, Guest. Please login or register.
Login with username, password and session length
News: Looking for a reliable webhosting provider? Read HostGator review to find 7 arguments in support of HostGator.
 
   Home   Help Search Login Register  
Data Structures and Algorithms Discussion Board > Data Structures, Algorithms, Java and C++ > Data Structures & Algorithms > Merge sort worst/best case and Quicksort in-situ
Pages: [1]
« previous next »
  Print  
Author Topic: Merge sort worst/best case and Quicksort in-situ  (Read 4195 times)
Rampage
Newbie
*

Rating: 0
Offline Offline

Posts: 1
« on: July 24, 2009, 08:09:43 AM »
Hello,
I have been googling the worst/best case of Merge sort lately but i can't seem to find what I'm looking for.My question is:
how to arrange an Array ( lets say (3,6,8,7,1)) so that Merge sort would do a max/min number of comparisons?

and an explanation to quick sort in-situ (with an example) would be appreciated!!

Thanks in Advance
Logged
anildas
Newbie
*

Rating: 0
Offline Offline

Posts: 3
« Reply #1 on: July 28, 2009, 11:13:15 AM »
Merging N elements take exactly N comparisons, irrespective of permutation of the elements. Therefore best and worst case of mergesort is the same.

That is my understanding. It should be easy enough to test this by taking some mergesort code and augmenting it to count comparisons.
Logged
Pages: [1]
  Print  
« previous next »
 
Jump to:  

 
Partners Ads        blu ray duplication        office chair