Category: Subjects

Boolean Algebra & Its Use in Computer Science

What Is Boolean Algebra And Why Is It Used in Computer Science?

 

George Boole, an English mathematician tried to find a way to express and simplify difficult algebraic algorithms and built a system called Boolean algebra.

 

What Is Boolean Algebra?

 

Boolean algebra is a mathematical system that consists of symbols that are used to understand the relativity between two contents.

The two logical variables are-

  • TRUE
  • FALSE

True is represented by 1 and false by 0.

Logic circuits are being designed by the use of Boolean Algebra. It is simple yet powerful part of Algebra that can be used for performing simple to complex analysis.

The following five types of operations can be performed with Boolean algebra-

  • NOT
  • AND
  • OR
  • NAND
  • NOR

 

NOT-

 

NOT gives the reverse outcome of the input that’s being made. For example, if you have given 1 as an input, NOT will generate the opposite as an output which is 0 and vice-versa. So, in total you can have two possible outcomes.

 

Input Output
0 1
1 0

NOT Table

 

AND-

 

With AND, you have to make two digits input and the output depends on them.

If you have given both 1 as input in AND operation, you will get 1 as an output otherwise the output will be zero.

 

Input 1 Input 2 Output
0 0 0
0 1 0
1 0 0
1 1 1

AND Table

 

OR-

 

With OR, you have to make two digits input and the output depends on them.

If one of the values given to OR operation is 1, then the output would be 1 otherwise 0.

 

Input-1 Input-2 Output
0 0 0
0 1 1
1 0 1
1 1 1

OR Table

 

NAND-

 

When you combine AND and NOT, the output is NAND. Together they form a cascade. If both the inputs are 1, then the output will be 0 otherwise all combinations will result in 1.

 

Input-1 Input-2 Output
0 0 1
0 1 1
1 0 1
1 1 0

NAND Table

 

NOR-

 

The combination of NOT and OR will result in NOR. It reverses the output of OR. When both the inputs are 0, that’s only way the output comes is 1. Rest of the inputs gets 0 as output.

 

Input-1 Input-2 Output
0 0 1
0 1 0
1 0 0
1 1 0

NOR Table

 

Basic Boolean Laws-

 

Boolean algebra comes with the set number of laws in order to simplify boolean expressions properly.

Basic Boolean Laws are as follows:

 

1. Idempotent Law-

 

A * A = A             (A variable AND with itself is always equal to the variable)

A + A = A            (A variable OR with itself is always equal to the variable)

 

2. Associative Law-

 

You can re-group the variables by removing the brackets-

 

(A * B) * C = A * (B * C)

(A + B) + C = A + (B + C)

 

3. Commutative Law-

 

Application order change doesn’t matter. It’s same one way or the other-

 

A * B = B * A

A + B = B + A

 

4. Distributive Law-

 

This law allows you to multiply or factor out the variables-

 

A * (B + C) = A * B + A * C

A + (B * C) = (A + B) * (A + C)

 

5. Identity Law-

 

A * 0 = 0     A * 1 = A          (A variable AND with 1 is always equal to the variable)

A + 1 = 1     A + 0 = A         (A variable OR with 0 is always equal to the variable)

 

6. Complement Law-

 

A * ~A = 0           (A variable AND with its complement is always equal to 0)

A + ~A = 1          (A variable OR with its complement is always equal to 1)

 

7. Involution Law-

 

~(~A) = A

 

8. DeMorgan’s Law-

 

~(A * B) = ~A + ~B

Two separate terms NAND together is the same as the two terms Complemented and OR

 

~(A + B) = ~A * ~B

Two separate terms NOR together is the same as the two terms Complemented and AND

 

9. Absorption-

 

In this law, like terms gets absorbed in order to simplify a complicated expression-

A + (A * B) = A

A * (A + B) = A

 

Each law is described by two parts that are duals of each other.

The duality Principle is Interchanging the + (OR) and * (AND) operations of the expression or interchanging the 0 and 1 variables of the expression and not changing the form of the variables.

 

Not everyone has the mathematical mind and simplifying such complex expressions can be very difficult for them. One needs help in such matters from time to time.

 

Boolean Algebra Calculator-

 

In order to make your life easy, Boolean Calculator is available online that can help you simply any boolean expression. You can easily find the truth table with its help.

Boolean Algebra Calculator is very ease to use. It can simplify any expression in no time. All you have to do is add an expression and press PARSE and that’s it.

The complicated Algebraic expression gets simple with a click and you get the result that you can use with what ever task you are performing.

 

Uses Of Boolean Algebra In Computer Science-

 

Boolean Algebra has wide range of usage in computer science world. A lot of programming is done with the help of Boolean Algebra. It consist of two expressions and their comparison.

 

For Example-

 

You will always get a true result 5 < 8 as 5 is always less than 8.

In x<6, you will only get the true result when x is a number that is less than 6 but a false result if x is a number that is equal to or greater than 6.

A<B is only true when A is a variable that is less than variable B. For programming purposes, other data types can also be used.

Overall, Boolean algebra has been very helpful in our lives.

 

AI Article Spinner

AI Article Spinner Can Fix Grammar & Sentence Structure With The Help Of NLP Paraphrasing Technology-

 

Creating unique and fresh content consistently is essential for an effective content marketing strategy. If you are not publishing new content on your online platform at a faster pace than your competition, your site will soon become irrelevant and search engines won’t rank it on their SERPs.

This is where an AI Article Spinner gives you an edge.

AI Article Spinners offer an excellent advantage to digital marketers in the content marketing space. With the Article Spinners, you can recreate a huge amount of content in a much shorter timeline.

 

What Is An AI Article Spinner?

 

AI and NLP technologies have taken the effectiveness of Article Spinners to a whole new level. Artificial Intelligence-based Article Spinners with Natural Language Processing (NLP) implemented on them help fix grammar and sentence structure along with paraphrasing the content.

AI Article Spinner is the best AI-based article spinner with NLP technology. This tool uses NLP and MLM algorithms to rewrite content in a rich and engaging way while maintaining its tone and central idea.

The result of rewriting from AI Article Spinner feels more natural and accurate than the output from Spinners that don’t incorporate AI during their processing.

 

Use Of NLP in AI Article Spinners-

 

In the past, machines were quite notorious for not understanding human language and emotions. Since computers operate on numbers, their natural language understanding capabilities were quite bad.

But with the latest advancements in AI, a new concept has emerged. NLP or Natural Language Processing is a revolutionary technology that helps machines hear, speak, understand, and interpret natural language in a written or verbal format.

NLP is becoming better day by day and it already has a lot of applications in many different domains.

The most notable application of NLP is for Article Spinners. This AI-based technology allows an Article Spinner to understand and text and rephrase it in a natural and human-friendly way.

 

Why Use An AI Article Spinner?

 

Let us go over some of the most useful benefits of AI Article Spinners with NLP.

 

01: Rephrasing With NLP-

 

NLP is an innovative technology that helps AI Article Spinners do rephrasing in a more natural and human-oriented way.

The rephrased content using these tools will look natural and will be completely understandable by humans.

Older Article Spinners didn’t have the AI features, so their output of rephrasing was quite bad. But with AI Article Spinners, you won’t have to worry about a robotic tone for your content.

These content spinners make it easier for content marketers to generate fresh content fast on a regular basis. AI Article Spinners fix grammar and sentence structure from a piece of content using NLP paraphrasing technology.

 

02: AI-Based Paraphrasing-

 

AI and NLP are correlated in the sense that NLP is the subset of AI. Artificial Intelligence has enabled developers to create software that is good at understanding human language and processing it.

The article spinner tools with AI offer an optimized way of creating content in bulk from existing ones. These spinners give you multiple variations for an existing piece of writing that you can use as it is or analyze to get inspiration for your future work.

AI & NLP-based paraphrasing allows the user to create unique and plagiarism-free content in an effective way.

 

03: Natural Tone-

 

The content tone matters the most when rephrasing it using a tool. The old article spinner technologies used to completely mess up the natural tone of the content by using a bad structure and weird choice of words.

The latest AI article spinners understand the content of content first and then rewrite it while keeping the central idea intact.

 

04. Proper Grammar & Sentence Structure-

 

One of the reasons why digital marketers shy away from the use of Article Spinners is because they supposedly create a bad sentence structure and mess up with the grammar quality.

The latest AI Paraphraser launched by AI Article Spinner use NLP paraphrasing to create a better content experience for the user with enhancing readability.

The output of AI-based article spinners is something that feels as good as human-written and the content doesn’t sound bland and dull. This is the power of AI-based article spinners and the reason why they are so popular.

 

05. Fast & Efficient Performance-

 

The biggest benefit of an AI Article Spinner is the fast and accurate performance.

A good article spinner should not be just fast, it should be able to do a good job in a short amount of time. Digital & Content Marketers love the AI article spinners because these tools help them create a lot of content in record time.

The content creation speed of article spinners makes them a desirable choice for everyone. Whether you are a student or an academic professional, or even a freelance writer, Article Spinners can help you create a lot of content in a swift and smooth manner.

 

06. Helps Save Time-

 

When you are on a deadline and you have to deliver an assignment or a piece of content fast, you can take help from Article Spinners to get inspiration for your work.

The use of Article Spinners for Academic and Digital Marketing purposes is only recommended when you are on a time crunch and you don’t have the choice to create content manually.

The AI Article Spinners help you save time in this scenario that you can utilize on the rest of your everyday tasks. AI Article Spinners help you meet deadlines and create content for your content marketing strategy.

 

Wrapping Up-

 

AI and NLP technologies are the future. These technologies are going to make it much simpler for humans and machines to interact with one another in a more natural way.

We are already seeing the example of this scenario with AI Article Spinners. We are quite excited about the future of AI Article Spinners and about how good they are going to get in the future.

 

Online AI-Based Paraphrasing Tools

How AI-Based Paraphrasing Tools Are Breaking Barriers In Writing Industry?

 

Paraphrasing technologies have come a long way over the past few years. The rephrasing performance of older paraphrasing tools was not so good in terms of content tone and readability.

But things have changed a lot now. With artificial technologies dominating the tech industry, the paraphrasing tools have also become much better.

AI-Based paraphrasing tools do a much better job of rewording sentences, paragraphs, essays, and articles. The rewritten content using these tools looks and feels completely natural to the reader.

 

Online Paraphrasing Tools With AI Technologies-

 

The latest AI-based paraphrasing tools are now much smarter at creating human-friendly content. These tools analyze the text and then rewrite it in a natural way while maintaining the central idea of the content.

These tools are made using the latest AI algorithms and are based on Machine Learning models. These paraphrasing software learn from the content and then base their output on what they’ve learned while processing the input text.

This is what makes AI paraphrasing tools so much better than the traditional word changer and rephrasing tools.

Here are some of the ways AI-based paraphrasing tools are completely changing the landscape of the writing industry.

 

01: Creating Quality Content Fast-

 

Manual writing is a time-consuming task especially when you have to write on a topic that has already been covered a lot on the internet. Coming up with unique words to express the same ideas, again and again, can get quite troublesome.

This is where AI-based paraphrasing tools come in. These tools enable you to get unlimited variations for the same piece of content. All the variations feel perfectly natural and engaging. These tools have made it possible for content marketers to generate quality content from existing ones in a fast and efficient way.

Although, there is no better alternative for manual writing, AI paraphrasing tools are your second-best choice if you want to create a lot of content fast.

If you want to create quality content from existing ones in a fast and efficient way, you should use the AI-based Paraphrasing Tool by Prepostseo. This tool runs on powerful AI algorithms that enable you to create high-quality content from input text in a short amount of time.

 

02: Completely Natural Content Tone-

 

The problem with paraphrasing and rewriting tools in the past was their unnatural tone. These tools were not good at creating a natural and human-friendly tone for the content. This is because these tools simply just changed the words in content with their synonyms, without keeping track of the readability.

AI-based paraphrasing tools use a better rewriting approach. These tools don’t just rewrite the content, they make sure to keep the content as natural as possible.

This is the reason why paraphrasing tools such as Prepostseo with AI technologies have become such a big hit. The output content that you get with these tools is readable and features a tone that comes off as perfectly natural.

 

03: Rich Vocabulary-

 

The key to using a rich vocabulary is to find just the right words to convey an idea that helps you do it in the most meaningful and understandable way.

Old paraphrasing tools technologies didn’t take this into account. These tools are used to change existing words with rare and difficult to pronounce words that don’t feel right.

AI-based paraphrasing tools keep the vocabulary rich, elegant, and yet easy to understand. These tools are all about creating quality content that works well for humans as well as for machines.

 

04: Automatic Content Generation Made Simple-

 

There is a lot of automatic content generation software out there. AI-based tools take the lead because of their easy-to-use interface and excellent content creation performance.

An AI-based tool will give you a content rewriting output that would feel close to how a human might write. These tools help their users generate a lot of content with ease.

Content creation in bulk is a huge undertaking. It can take a lot of time if you decide to do it manually. If you have some content and you to rewrite it, using an AI-based paraphrasing tool will be a great choice. Using these tools, you can create rich and engaging content in a short amount of time.

The paraphrasing performance is different for different tools. If you want to rewrite content that is 100% unique, give a chance to Paraphraser.io. This tool is quite great at automatic content generation using AI algorithms.

 

05: 100% Unique Content With No Plagiarism-

 

The biggest reason why AI-based paraphrasing tools are so popular is that they help to remove plagiarism from a piece of content.

Although the older paraphrasing technologies also remove the plagiarism from the content by rewriting it, the rewritten content just doesn’t look good.

With AI tools, the paraphrased content that you get from them is 100% unique and free from plagiarism. These tools make it easier and simpler for a user to remove plagiarism from a piece of content while maintaining its quality.

 

06: Excellent Readability-

 

Readability is one of the most important factors that make up good content. It doesn’t matter how great your content is, it won’t work well if it is not easily readable.

The AI-based paraphrasing tools help you create high-quality content that feels completely readable. Some of these tools also give you the readability report for the content that you can check out to see whether your content is readable or not.

Older paraphrasing technologies didn’t consider the readability of the content when rewording it. This is one of the areas where the latest paraphrasing tools with AI technologies stand out.

 

Wrapping Up-

 

AI-based paraphrasing tools are a ground-breaking technology that is completely going to change the way digital marketers used to come up with unique and engaging content.

These technologies are going to automate the entire content creation process and will prove to be extremely time-efficient in the future. AI technology has certainly taken the performance of paraphrasing tools to a whole new level.

 

Bubble Sort Algorithm | Example | Time Complexity

Bubble Sort-

 

  • Bubble sort is the easiest sorting algorithm to implement.
  • It is inspired by observing the behavior of air bubbles over foam.
  • It is an in-place sorting algorithm.
  • It uses no auxiliary data structures (extra space) while sorting.

 

How Bubble Sort Works?

 

  • Bubble sort uses multiple passes (scans) through an array.
  • In each pass, bubble sort compares the adjacent elements of the array.
  • It then swaps the two elements if they are in the wrong order.
  • In each pass, bubble sort places the next largest element to its proper position.
  • In short, it bubbles down the largest element to its correct position.

 

Bubble Sort Algorithm-

 

The bubble sort algorithm is given below-

 

for(int pass=1 ; pass<=n-1 ; ++pass)     // Making passes through array
{
    for(int i=0 ; i<=n-2 ; ++i)
    {
        if(A[i] > A[i+1])                // If adjacent elements are in wrong order
            swap(i,i+1,A);               // Swap them
    }
}

//swap function : Exchange elements from array A at position x,y

void swap(int x, int y, int[] A)
{
    int temp = A[x];
    A[x] = A[y];
    A[y] = temp;
    return ;
}

// pass : Variable to count the number of passes that are done till now
// n : Size of the array
// i : Variable to traverse the array A
// swap() : Function to swap two numbers from the array
// x,y : Indices of the array that needs to be swapped

 

Bubble Sort Example-

 

Consider the following array A-

 

 

Now, we shall implement the above bubble sort algorithm on this array.

 

Step-01:

 

  • We have pass=1 and i=0.
  • We perform the comparison A[0] > A[1] and swaps if the 0th element is greater than the 1th element.
  • Since 6 > 2, so we swap the two elements.

 

 

Step-02:

 

  • We have pass=1 and i=1.
  • We perform the comparison A[1] > A[2] and swaps if the 1th element is greater than the 2th element.
  • Since 6 < 11, so no swapping is required.

 

 

Step-03:

 

  • We have pass=1 and i=2.
  • We perform the comparison A[2] > A[3] and swaps if the 2nd element is greater than the 3rd element.
  • Since 11 > 7, so we swap the two elements.

 

 

Step-04:

 

  • We have pass=1 and i=3.
  • We perform the comparison A[3] > A[4] and swaps if the 3rd element is greater than the 4th element.
  • Since 11 > 5, so we swap the two elements.

 

 

Finally after the first pass, we see that the largest element 11 reaches its correct position.

 

Step-05:

 

  • Similarly after pass=2, element 7 reaches its correct position.
  • The modified array after pass=2 is shown below-

 

 

Step-06:

 

  • Similarly after pass=3, element 6 reaches its correct position.
  • The modified array after pass=3 is shown below-

 

 

Step-07:

 

  • No further improvement is done in pass=4.
  • This is because at this point, elements 2 and 5 are already present at their correct positions.
  • The loop terminates after pass=4.
  • Finally, the array after pass=4 is shown below-

 

 

Optimization Of Bubble Sort Algorithm-

 

  • If the array gets sorted after a few passes like one or two, then ideally the algorithm should terminate.
  • But still the above algorithm executes the remaining passes which costs extra comparisons.

 

Optimized Bubble Sort Algorithm-

 

The optimized bubble sort algorithm is shown below-

 

for (int pass=1 ; pass<=n-1 ; ++pass)
{
    flag=0                                // flag denotes are there any swaps done in pass

    for (int i=0 ; i<=n-2 ; ++i)
    {
        if(A[i] > A[i+1])
        {
            swap(i,i+1,A);
            flag=1                        // After swap, set flag to 1
        }
    }

    if(flag == 0) break;                  // No swaps indicates we can terminate loop
}

void swap(int x, int y, int[] A)
{
    int temp = A[x];
    A[x] = A[y];
    A[y] = temp;
    return;
}

 

Explanation-

 

  • To avoid extra comparisons, we maintain a flag variable.
  • The flag variable helps to break the outer loop of passes after obtaining the sorted array.
  • The initial value of the flag variable is set to 0.
  • The zero value of flag variable denotes that we have not encountered any swaps.
  • Once we need to swap adjacent values for correcting their wrong order, the value of flag variable is set to 1.
  • If we encounter a pass where flag == 0, then it is safe to break the outer loop and declare the array is sorted.

 

Time Complexity Analysis-

 

  • Bubble sort uses two loops- inner loop and outer loop.
  • The inner loop deterministically performs O(n) comparisons.

 

Worst Case-

 

  • In worst case, the outer loop runs O(n) times.
  • Hence, the worst case time complexity of bubble sort is O(n x n) = O(n2).

 

Best Case-

 

  • In best case, the array is already sorted but still to check, bubble sort performs O(n) comparisons.
  • Hence, the best case time complexity of bubble sort is O(n).

 

Average Case-

 

  • In average case, bubble sort may require (n/2) passes and O(n) comparisons for each pass.
  • Hence, the average case time complexity of bubble sort is O(n/2 x n) = Θ(n2).

 

The following table summarizes the time complexities of bubble sort in each case-

 

Time Complexity
Best Case O(n)
Average Case Θ(n2)
Worst Case O(n2)

 

From here, it is clear that bubble sort is not at all efficient in terms of time complexity of its algorithm.

 

Space Complexity Analysis-

 

  • Bubble sort uses only a constant amount of extra space for variables like flag, i, n.
  • Hence, the space complexity of bubble sort is O(1).
  • It is an in-place sorting algorithm i.e. it modifies elements of the original array to sort the given array.

 

Properties-

 

Some of the important properties of bubble sort algorithm are-

  • Bubble sort is a stable sorting algorithm.
  • Bubble sort is an in-place sorting algorithm.
  • The worst case time complexity of bubble sort algorithm is O(n2).
  • The space complexity of bubble sort algorithm is O(1).
  • Number of swaps in bubble sort = Number of inversion pairs present in the given array.
  • Bubble sort is beneficial when array elements are less and the array is nearly sorted.

 

PRACTICE PROBLEMS BASED ON MERGE SORT ALGORITHM-

 

Problem-01:

 

The number of swapping needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order using bubble sort is-  (ISRO CS 2017)

  1. 11
  2. 12
  3. 13
  4. 10

 

Solution-

 

In bubble sort, Number of swaps required = Number of inversion pairs.

Here, there are 10 inversion pairs present which are-

  1. (8,7)
  2. (22,7)
  3. (22,9)
  4. (8,5)
  5. (22,5)
  6. (7,5)
  7. (9,5)
  8. (31,5)
  9. (22,13)
  10. (31,13)

 

Thus, Option (D) is correct.

 

Problem-02:

 

When will bubble sort take worst-case time complexity?

  1. The array is sorted in ascending order.
  2. The array is sorted in descending order.
  3. Only the first half of the array is sorted.
  4. Only the second half of the array is sorted.

 

Solution-

 

  • In bubble sort, Number of swaps required = Number of inversion pairs.
  • When an array is sorted in descending order, the number of inversion pairs = n(n-1)/2 which is maximum for any permutation of array.

 

Thus, Option (B) is correct.

 

To gain better understanding about Bubble Sort Algorithm,

Watch this Video Lecture

 

Next Article- Insertion Sort

 

Other Popular Sorting Algorithms-

 

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Merge Sort Algorithm | Example | Time Complexity

Merge Sort-

 

  • Merge sort is a famous sorting algorithm.
  • It uses a divide and conquer paradigm for sorting.
  • It divides the problem into sub problems and solves them individually.
  • It then combines the results of sub problems to get the solution of the original problem.

 

How Merge Sort Works?

 

Before learning how merge sort works, let us learn about the merge procedure of merge sort algorithm.

The merge procedure of merge sort algorithm is used to merge two sorted arrays into a third array in sorted order.

 

Consider we want to merge the following two sorted sub arrays into a third array in sorted order-

 

 

The merge procedure of merge sort algorithm is given below-

 

// L : Left Sub Array , R : Right Sub Array , A : Array

merge(L, R, A)
{
    nL = length(L)    // Size of Left Sub Array
    nR = length(R)    // Size of Right Sub Array

    i = j = k = 0

    while(i<nL && j<nR)
    {
      /* When both i and j are valid i.e. when both the sub arrays have elements to insert in A */
      
       if(L[i] <= R[j])
       {
          A[k] = L[i]
          k = k+1
          i = i+1
       }
       else
       {
          A[k] = R[j]
          k = k+1
          j = j+1
       }
    }

    // Adding Remaining elements from left sub array to array A
    while(i<nL)
    {
       A[k] = L[i]
       i = i+1
       k = k+1
    }

    // Adding Remaining elements from right sub array to array A
    while(j<nR)
    {
       A[k] = R[j]
       j = j+1
       k = k+1
    }
}

 

The above merge procedure of merge sort algorithm is explained in the following steps-

 

Step-01:

 

  • Create two variables i and j for left and right sub arrays.
  • Create variable k for sorted output array.

 

 

Step-02:

 

  • We have i = 0, j = 0, k = 0.
  • Since L[0] < R[0], so we perform A[0] = L[0] i.e. we copy the first element from left sub array to our sorted output array.
  • Then, we increment i and k by 1.

 

Then, we have-

 

 

Step-03:

 

  • We have i = 1, j = 0, k = 1.
  • Since L[1] > R[0], so we perform A[1] = R[0] i.e. we copy the first element from right sub array to our sorted output array.
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-04:

 

  • We have i = 1, j = 1, k = 2.
  • Since L[1] > R[1], so we perform A[2] = R[1].
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-05:

 

  • We have i = 1, j = 2, k = 3.
  • Since L[1] < R[2], so we perform A[3] = L[1].
  • Then, we increment i and k by 1.

 

Then, we have-

 

 

Step-06:

 

  • We have i = 2, j = 2, k = 4.
  • Since L[2] > R[2], so we perform A[4] = R[2].
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-07:

 

  • Clearly, all the elements from right sub array have been added to the sorted output array.
  • So, we exit the first while loop with the condition while(i<nL && j<nR) since now j>nR.
  • Then, we add remaining elements from the left sub array to the sorted output array using next while loop.

 

Finally, our sorted output array is-

 

 

Basically,

  • After finishing elements from any of the sub arrays, we can add the remaining elements from the other sub array to our sorted output array as it is.
  • This is because left and right sub arrays are already sorted.

 

Time Complexity

The above mentioned merge procedure takes Θ(n) time.

This is because we are just filling an array of size n from left & right sub arrays by incrementing i and j at most Θ(n) times.

 

Merge Sort Algorithm-

 

Merge Sort Algorithm works in the following steps-

  • It divides the given unsorted array into two halves- left and right sub arrays.
  • The sub arrays are divided recursively.
  • This division continues until the size of each sub array becomes 1.
  • After each sub array contains only a single element, each sub array is sorted trivially.
  • Then, the above discussed merge procedure is called.
  • The merge procedure combines these trivially sorted arrays to produce a final sorted array.

 

The division procedure of merge sort algorithm which uses recursion is given below-

 

// A : Array that needs to be sorted

MergeSort(A)
{
   n = length(A)
   if n<2 return
   mid = n/2
   left = new_array_of_size(mid)       // Creating temporary array for left
   right = new_array_of_size(n-mid)    // and right sub arrays

   for(int i=0 ; i<=mid-1 ; ++i)
   {
      left[i] = A[i]                  // Copying elements from A to left
   }

   for(int i=mid ; i<=n-1 ; ++i)
   {
      right[i-mid] = A[i]             // Copying elements from A to right
   }

   MergeSort(left)                    // Recursively solving for left sub array
   MergeSort(right)                   // Recursively solving for right sub array

   merge(left, right, A)              // Merging two sorted left/right sub array to final array
}

 

Merge Sort Example-

 

Consider the following elements have to be sorted in ascending order-

6, 2, 11, 7, 5, 4

 

The merge sort algorithm works as-

 

 

Time Complexity Analysis-

 

In merge sort, we divide the array into two (nearly) equal halves and solve them recursively using merge sort only.

So, we have-

 

 

Finally, we merge these two sub arrays using merge procedure which takes Θ(n) time as explained above.

 

If T(n) is the time required by merge sort for sorting an array of size n, then the recurrence relation for time complexity of merge sort is-

 

 

On solving this recurrence relation, we get T(n) = Θ(nlogn).

Thus, time complexity of merge sort algorithm is T(n) = Θ(nlogn).

 

Also Read- Master’s Theorem for Solving Recurrence Relations

 

Space Complexity Analysis-

 

  • Merge sort uses additional memory for left and right sub arrays.
  • Hence, total Θ(n) extra memory is needed.

 

Properties-

 

Some of the important properties of merge sort algorithm are-

  • Merge sort uses a divide and conquer paradigm for sorting.
  • Merge sort is a recursive sorting algorithm.
  • Merge sort is a stable sorting algorithm.
  • Merge sort is not an in-place sorting algorithm.
  • The time complexity of merge sort algorithm is Θ(nlogn).
  • The space complexity of merge sort algorithm is Θ(n).

 

NOTE

Merge sort is the best sorting algorithm in terms of time complexity Θ(nlogn)

if we are not concerned with auxiliary space used.

 

PRACTICE PROBLEMS BASED ON MERGE SORT ALGORITHM-

 

Problem-

 

Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? (GATE 2015)

  1. 256
  2. 512
  3. 1024
  4. 2048

 

Solution-

 

We know, time complexity of merge sort algorithm is Θ(nlogn).

 

Step-01:

 

It is given that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64.

So, we have-

 

k x nlogn = 30                   (for n = 64)

k x 64 log64 = 30

k x 64 x 6 = 30

From here, k = 5 / 64.

 

Step-02:

 

Let n be the maximum input size of a problem that can be solved in 6 minutes (or 360 seconds).

Then, we have-

 

k x nlogn = 360

(5/64) x nlogn = 360         { Using Result of Step-01 }

nlogn = 72 x 64

nlogn = 4608

On solving this equation, we get n = 512.

 

Thus, correct option is (B).

 

To gain better understanding about Merge Sort Algorithm,

Watch this Video Lecture

 

Next Article- Quick Sort

 

Other Popular Sorting Algorithms-

 

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.