3

Merge Sort

Definition:

Merge Sort is a type of sorting algorithm. It is a divide and conquer algorithm and  it was invented by John von Neumann.

In worst, average and best case its time complexity is O(n logn).

Its Properties in short:

  • Stable,
  • Completed,
  • O(n logn) time complexity,
  • O ( n ) extra space for arrays,
  • O ( logn ) extra space for linked lists,
  • Does not require random access data,
  • Not adaptive.

How does it work?

In merge sort,

  1. Firstly, unsorted array is divided into n sublist, until each sublist has only 1 element,
  2. Then all elements are merged according to their value and new sorted arrays are created.

In the figure below, you can see animated merge sort example.

Merge-sort

Animated Merge Sort Example

Another example for merge sort is:

Merge_sort_algorithm_diagram.svg

          Example For Merge Sort

Animation:

For better understanding, go to this animation page.

Pseudocode:

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

 

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/merge-sort

Figures from:  http://en.wikipedia.org

 

For more algorithms, go to Algorithms Section.

omersezer

3 Comments

  1. I have read so many posts regarding the blogger lovers except
    this post is actually a good piece of writing, keep it up.

Leave a Reply

Your email address will not be published. Required fields are marked *