**rach wrote:****rachellgrace wrote:**- Can you suggest guys another way of sorting data?

invented by Donald Shell

Algorithm

start separation = number of elements / 2

compare a[i] and a[i+separation]

swap if necessary

do for each element of array i = 0 to a.length – separation

set separation = separation /2

recompare all the elements

separation calculation

shell suggested /2

other sequences give great improvement

note figure 7.3 does not / 2 properly

Code Methods: shellsort

Average Case Shellsort : Open Problem

Mergesort

Code Methods: mergesort (2), merge

Worst Case: O(NlogN)

Recursively merges two sorted lists

Time to merge two sorted lists is linear (N-1 comparisons)

1 13 24 26 merge 2 15 27 38 gives 1 2 13 15 24 26 27 38

Classic Divide and Conquer Strategy

If more than one element, divide and merge sort the first and second

half

Analysis

Recurrance Relation

T(1) = 1

T(N) = 2T(N/2) + N

T(N)/ N = T(N/2)/N/2 + 1

T(N/2) / N/2 = T(N/4) / N/4 + 1

T(2) / 2 = T(1)/1 + 1

Sum up all of the equations

T(N)/N = T(1)/1 + logN <- this logN is the sum of the 1’s

T(N) = NlogN + N = O(NlogN)

Uses extra memory to merge and copy back into array

Merging is cornerstone of external sorting routines

Not often used for main memory sorts

Can also do it not recursively

Or can use less memory – much more complex algorithm (impractical)