Merge Sort Assignment Help

Merge sort is definitely an O (n log n) comparison-based sorting algorithm. Most implementations create a stable sort, meaning the actual implementation preserves the input order associated with equal elements within the sorted output. Merge sort is really a divide as well as conquer algorithm.

Merge Sort Algorithm :

Divide: If S has at least two elements (nothing needs to be done if S has zero or one elements), remove all the elements from S and put them into two sequences, S1 and S2, each containing about half of the elements of S.

Conquer: Sort sequences S1 and S2 using Merge Sort.

Combine: Put back the elements into S by merging the sorted sequences S1 and S2 into one sorted sequence

Sorting Problem:

Sort a series associated with n elements into non-decreasing purchase.

• Divide: Divide the n-element sequence to be sorted into two subsequences associated with n/2 elements each
• Conquer: Sort the both subsequences recursively utilizing merge sort.
• Combine: Merge both categorized subsequences to create the actual categorized solution.
  
  

Merge-Sort (A, p, r)

INPUT: a sequence of n numbers stored in array A

OUTPUT: an ordered sequence of n numbers

Merge-Sort Example