Step-by-Step Guide to Merge Sort Using Ballerina

Faria KarimFaria Karim
3 min read

Merge Sort Using Ballerina:

Sorting algorithms are important in programming, especially for organizing large amounts of data. Merge Sort is a popular and efficient sorting method because it uses a "divide and conquer" approach, giving it a time complexity of O(n log n). In this blog, we’ll look at how Merge Sort works and how to code it in the Ballerina programming language.

What is Merge Sort?:

Merge Sort is a sorting method that uses a divide-and-conquer strategy. It repeatedly splits the input array into smaller subarrays, sorts those subarrays, and then combines them back together to create a sorted array.

Steps Of Merge Sort:

  1. The main concept is to repeatedly split the list or array into two halves until it cannot be divided any further, and then merge them back together in sorted order.

  2. Start with the entire array and find the midpoint of the array.

  3. Split the array into two halves: the left half and the right half.

  4. Continue calling the mergeSort function recursively on each half until only one element remains.

  5. Call the merge function to merge two divided arrays into one in sorted order.

  6. To merge the arrays, create an empty array to hold the sorted elements.

  7. Use two pointers to keep track of the current index in both the left and right arrays.

  8. If the element in the left array is smaller or equal, add it to the sorted array and move the pointer in the left array to the next element.

  9. Otherwise the element in the right array is smaller, add it to the sorted array and move the pointer in the right array to the next element.

  10. Continue comparing and adding elements until all elements from both arrays have been added to the sorted array.

  11. Repeat the merging process for all the sorted subarrays until we have one fully sorted array.

Implementation of Merge Sort in Ballerina:

  1. Start by creating a new Ballerina project.

  2. Open a terminal and enter the following command: bal new merge_sort_example.

  3. Open the main.bal file and write the Merge Sort code.

  4. Save the code and run the program using this command in the terminal: bal run.

Code Snippet:

Following is the coding implementation of merge sort:

import ballerina/io;

// Function to merge two sorted arrays
function merge(int[] left, int[] right) returns int[] {
    int[] result = [];
    int i = 0;
    int j = 0;

    // Compare elements from both arrays and merge in sorted order into one array
    while i < left.length() && j < right.length() {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }

    // Append any remaining elements from the left or right array
    while i < left.length() {
        result.push(left[i]);
        i += 1;
    }

    while j < right.length() {
        result.push(right[j]);
        j += 1;
    }

    return result;
}

// Function to implement Merge Sort and divide the array
function mergeSort(int[] arr) returns int[] {
    // If the array has only one element, then it is already sorted. So return the array
    if arr.length() <= 1 {
        return arr;
    }

    // Find the midpoint of the array to divide into halves
    int mid = arr.length() / 2;

    // Split the array into two halves
    int[] leftHalf = arr.slice(0, mid);
    int[] rightHalf = arr.slice(mid, arr.length());

    // Recursively divide and sort both halves
    int[] sortedLeft = mergeSort(leftHalf);
    int[] sortedRight = mergeSort(rightHalf);

    // Merge the sorted halves into one array
    return merge(sortedLeft, sortedRight);
}

public function main() {
    int[] arr = [38, 27, 43, 3, 9, 82, 10];

    // Sort the array using Merge Sort
    int[] sortedArr = mergeSort(arr);

    io:println("Sorted Array Using Merge Sort: ", sortedArr);
}

Time and Space Complexity:

Time complexity: O(nlogn)

Space complexity: O(n)

0
Subscribe to my newsletter

Read articles from Faria Karim directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Faria Karim
Faria Karim

Currently, I am working as an "Associate Software Engineer" at "Kaz Software". I have completed my graduation from North South University in the year 2020 with the highest distinction. I always love to explore new ideas. I am a curious and self-motivated person. So, I always try to keep learning and share my ideas with other people. I enjoy problem-solving a lot. I have solved around 100+ problems in various online judges and I am also a three-star coder at Hackerrank. Moreover, I have participated in the ACM ICPC two times. I have completed the off-sight round of ACM ICPC of 2018. I have some basic knowledge of c/c++, Java, Javascript, Php, and Python. I have done several projects using these programming languages. I have hands-on experience on various backend frameworks like Node.js, Django, Flask, and Laravel. I have also used React.js as the front-end library for a few of my projects. Currently, I am more into React.js. For web-based projects, I have worked on both MySQL and NoSQL (MongoDB) as the database system. Machine learning is my another matter of interest. I have research experience in the fuzzy system. I have done a few projects using Tensorflow, Keras, CNN, and LSTM. Recently I have grown my interest in game development. I have built two games. One is using construct 2 and the another one is in Unity 3D. Side by side, I am also trying to figure out the things on ionic. In my free time, I mostly like to surf the internet, watch movies, and also love to do animations and illustrations using Powerpoint.