• Mergesort

• NOTE: Your Device may work slower on a large Dataset!

• • # of Data

  • Sync
  • Randomize
  • Sort

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

How it works

Mergesort is an efficient, general-purpose, and comparison-based sorting algorithm. Conceptually, a merge sort works as follows:

1. Keep dividing the unsorted list into n sublists, until they each contain one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

Pseudocode Implementation

Merge(LA as Array, RA as Array, A as Array) {
    nL = Length of LeftArray (LA)
    nR = Length of RightArray (RA)
    i = j = k = 0
    while(i<nL and j<nR) {
        if(LA[i] <= RA[j]) {
            A[k] = LA[i]
            i = i+1
        }
        else {
            A[k] = RA[j]
            j = j+1
        }
        k = k+1
    }
    while(i<nL) {
        A[k] = LA[i]
        i = i+1
        k = k+1
    }
    while(j<nR) {
        A[k] = RA[j]
        j = j+1
        k = k+1
    }
}

MergeSort(A as Array) {
    n = length of Array (A)
    if(n<2)
        return
    mid = n/2
    left = array of size(mid)
    right = array of size(n-mid)
    for i = 0 to mid-1
        left[i] = A[i]
    for i = mid to n-1
        right[i-mid] = A[i]
    MergeSort(left)
    MergeSort(right)
    Merge(left, right, A)
}

Source: https://fullyunderstood.com/pseudocodes/merge-sort/

Source: https://en.wikipedia.org/wiki/Merge_sort