Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Merge Sort

    Merge sort is one of the fastest sorting algorithms. Many applications use some versions of merge sort in production. We have discussed algorithms that run in quadratic time like Bubble sort or Selection sort. Merge sort is way faster than all the quadratic sorting algorithms and runs in time.
    notion image
    Merge sort is a divide-and-conquer algorithm that recursively sorts parts of the given array and merges those together. The core of the algorithm is the efficient algorithm to merge two sorted arrays into a single sorted array. During its work, the merge sort algorithm splits the array into two parts. Then recursively sorts the first part. After which recursively sorts the second part. Then merges those two sorted arrays into one sorted array:
    def merge(a, b):
        i, j, res = 0, 0, []                # Index for a and b with resulting array
        while i < len(a) or j < len(b):     # While there are still elements left
            ai = a[i] if i < len(a) else float('inf')
            bj = b[j] if j < len(b) else float('inf')
    
            if ai < bj:                     # If a[i] < b[j] => take a[i]
                res.append(ai)              # Add a[i] to result
                i += 1                      # Move to the next element
            else:                           # If a[i] >= b[j] => take b[j]
                res.append(bj)              # Add b[j] to result
                j += 1                      # Move to the next element
        return res
    
    
    def merge_sort(a):
        if len(a) <= 1:                     # Nothing to sort
            return a                        # Return the initial array
    
        l = merge_sort(a[: len(a) // 2])    # Sort the left part
        r = merge_sort(a[len(a) // 2:])     # Sort the right part
        return merge(l, r)
    At each stage, the algorithm takes the array, splits it into 2 parts, sorts those separately, and merges the resulting arrays into a new one. Note that all the previous algorithms discussed changed the initial array in place (modified it without creating a new one), while the merge sort algorithm creates a new array on each iteration. To make the merge sort algorithm perform an in-place sorting, we would need to modify the algorithm and the merge() function to merge two consecutive blocks of the initial array using only indices. Can you do that 😎?
    Let’s simulate the algorithm on several arrays:
    [4, 1, -1, 0, 2, 8]
    1. merge_sort([4, 1, -1, 0, 2, 8]):
      1. merge_sort([4, 1, -1])
      2. merge_sort([0, 2, 8])
    1. merge_sort([4, 1, -1]):
      1. merge_sort([4]) β†’ return [4]
      2. merge_sort([1, -1])
    1. merge_sort([1, -1]):
      1. merge_sort([1]) β†’ return [1]
      2. merge_sort([-1]) β†’ return [-1]
    1. Back to merge_sort([1, -1]) β†’ return [-1, 1]
    1. Back to merge_sort([4, 1, -1]) β†’ return [-1, 1, 4]
    1. merge_sort([0, 2, 8]):
      1. merge_sort([0]) β†’ return [0]
      2. merge_sort([2, 8])
    1. merge_sort([2, 8]):
      1. merge_sort([2]) β†’ return [2]
      2. merge_sort([8]) β†’ return [8]
    1. Back to merge_sort([2, 8]) β†’ return [2, 8]
    1. Back to merge_sort([0, 2, 8]) β†’ return [0, 2, 8]
    1. Back to merge_sort([4, 1, -1, 0, 2, 8]) β†’ return [-1, 0, 1, 2, 4, 8]

    Challenge

    Given an array of n integers, you are asked to sort them in descending order using the Merge Sort algorithm.

    Input

    The first line of the input contains a single integer n (1 ≀ n ≀ 100 000).
    The next line contains n space-separated integers ( ≀ ≀ ) representing the initial array.

    Output

    The program should print n space-separated integers in descending order.

    Examples

    Input
    Output
    4 7 4 9 1
    9 7 4 1
    5 -4 8 2 -3 6
    8 6 2 -3 -4
    Β 

    Constraints

    Time limit: 2.5 seconds

    Memory limit: 512 MB

    Output limit: 10 MB

    To check your solution you need to sign in
    Sign in to continue