CODEWITHSUNDEEP
algorithmsorting
Shaon Hasan
Shaon Hasan

Reputation: 740

How does the Pseudocode for merge sort work?

I have got this Pseudocode for merge sort. But not really clear how it works. can anyone please explain to me?

for i=1 ; i<size ; i=2i
   for j=0 ; j<size - i ; j= j+2i
     Merge(&A[j] , i , min(2i,size-j))

And the Merge() method is:

Merge(A, end1, end2)
  i = 0; j = end1 ; k =0

while i<end1 and j<end2
  if(A[i] < A[j])
    temp[k] = A[i]
  else
     temp[k] = A[j]
     j = j+1, k=k+1

while i<end1
   temp[k] = A[i]
   i = i+1 , k=k+1

while j<end2
   temp[k] = A[j]
   j = j+1 , k=k+1

for(i=0 ; i<end2; i++)
    A[i] = temp[i]

Source: http://www.youtube.com/watch?v=GCae1WNvnZM&list=PL89B61F78B552C1AB&index=4

if anyone can give me better source for algorithm tutorials, that wud be awsome too.. Thanks in advance. :-)

Upvotes: 0

Views: 1917

Answers (2)

user1196549
user1196549

Reputation:

Let us start with the merge operation: it takes as input two sequences that are stored contiguously. The function copies to temporary storage all the elements from both sequences, always choosing the smallest of the two (when either sequence is exhausted, the copy continues with the other sequence). Then all elements are copied back to the original storage.

If you admit that the two input sequences are provided in sorted order, the result of the merge is a single sorted sequence.

Now the main program. It is formed of two nested loops. The outer one monitors the length of the sequences, starting from 1, and doubles it every time. The inner loop takes two sequences at a time, computing where they are stored, and merges them into a single.

And here comes the magic of MergeSort: initially, all elements form sequences of 1 element, which are obviously sorted. After one pass (the inner loop), you get sorted sequences of 2 elements. Then of 4... until there remains a single sorted sequence.

|e|b|g|h|c|a|f|d|
|be|gh|ac|df|
|begh|acdf|
|abcdefgh|

Upvotes: 1

Alexey Malev
Alexey Malev

Reputation: 6533

The idea is the following:

mergesort(array) can be defined as:

  • We sort the small arrays manually (the exact meaning of manually and small varies - for example we can sort array of 2 elements by comparing and swapping it if necessary).
  • If the array is not small, we split it in two halves and do mergesort for each part separately;
  • When sorting of both halves are done, we merge the results in linear time (put all elements into the array, preferring smaller to bigger);

Merge sort wiki page may be useful. Also if you're interested with algorithms, try reading this book, it is really awesome.

Upvotes: 0

Related Questions