The Survival of Advanced Programmers The Use of Merge Sort

Let’s introduce the use of merge sort in detail, mainly analyze the examples in various language environments, please refer to it! ! !

1. Merge sort (Merge sort) is an efficient sorting algorithm based on the merge operation. This algorithm is a very typical application of Divide and Conquer.

As a typical algorithm application of the idea of ​​divide and conquer, the implementation of merge sort consists of two methods:

  • Top-down recursion (all recursive methods can be rewritten with iteration, so there is a second method);
  • bottom-up iteration;

In “Description of Data Structures and Algorithms in JavaScript”, the author gives a bottom-up iterative approach. But for the recursive method, the author believes that:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

    However, this is not feasible in JavaScript because the recursion depth of this algorithm is too deep for it.

To be honest, I don’t quite understand this sentence. Does it mean that the memory of the JavaScript compiler is too small, and the recursion is too deep to cause memory overflow? I hope there is a god who can teach me.

Like selection sort, the performance of merge sort is not affected by the input data, but it performs much better than selection sort because it is always O(nlogn) time complexity. The tradeoff is that additional memory space is required.

2. Algorithm steps

  1. Apply for space to be the sum of the two sorted sequences, and this space is used to store the merged sequence;

  2. Set two pointers, the initial positions are the starting positions of the two sorted sequences;

  3. Compare the elements pointed to by the two pointers, select a relatively small element into the merge space, and move the pointer to the next position;

  4. Repeat step 3 until a pointer reaches the end of the sequence;

  5. Copies all remaining elements of the other sequence directly to the end of the merged sequence.

3. Code implementation

JavaScript instance

function  mergeSort ( arr ) {   // use top-down recursion 
    var len = arr.length;
     if (len < 2 ) {
         return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

Python instance

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

Go instance

func mergeSort(arr []int) []int {
        length := len(arr)
        if length < 2 {
                return arr
        }
        middle := length / 2
        left := arr[0:middle]
        right := arr[middle:]
        return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
        var result []int
        for len(left) != 0 && len(right) != 0 {
                if left[0] <= right[0] {
                        result = append(result, left[0])
                        left = left[1:]
                } else {
                        result = append(result, right[0])
                        right = right[1:]
                }
        }

        for len(left) != 0 {
                result = append(result, left[0])
                left = left[1:]
        }

        for len(right) != 0 {
                result = append(result, right[0])
                right = right[1:]
        }

        return result
}

Java instance

public class MergeSort implements IArraySort {

    @Override 
    public  int [] sort( int [] sourceArray) throws Exception {
         // Copy arr without changing the parameter content 
        int [] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

PHP example

function mergeSort($arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right)
{
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left))
        $result[] = array_shift($left);

    while (count($right))
        $result[] = array_shift($right);

    return $result;
}

C example

int min(int x, int y) {
    return x < y ? x : y;
}
void  merge_sort ( int arr[], int len)  {
     int *a = arr;
    int *b = ( int *) malloc (len * sizeof ( int ));
    int seg, start;
    for (seg = 1 ; seg < len; seg += seg) {
         for (start = 0 ; start < len; start += seg * 2 ) {
             int low = start, mid = min(start + seg, len), high = min(start + seg * 2 , len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

C++ example

template < typename T> // Both integers and floating-point numbers can be used, if you want to use the object (class), you must set the "less than" (<) operator function 
void  merge_sort (T arr[], int len)  {
    T *a = arr;
    T *b = new T[len];
    for ( int seg = 1 ; seg < len; seg += seg) {
         for ( int start = 0 ; start < len; start += seg + seg) {
             int low = start, mid = min(start + seg, len ), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

C# example

public static List<int> sort(List<int> lst) {
    if (lst.Count <= 1)
        return lst;
    int mid = lst.Count / 2;
    List< int > left = new List< int >();   // Define the left List 
    List< int > right = new List< int >(); // Define the right List 
    // The following two loops divide lst into Left and right two List 
    for ( int i = 0 ; i < mid; i++)
        left.Add(lst[i]);
    for (int j = mid; j < lst.Count; j++)
        right.Add(lst[j]);
    left = sort(left);
    right = sort(right);
    return merge(left, right);
}
///  <summary> 
/// Merge two sorted Lists 
///  </summary> 
///  <param > Left List </param> 
///  <param > Right List </param> 
///  <returns> </returns> 
static List< int > merge ( List< int > left, List< int > right ) {
    List<int> temp = new List<int>();
    while (left.Count > 0 && right.Count > 0) {
        if (left[0] <= right[0]) {
            temp.Add(left[0]);
            left.RemoveAt(0);
        } else {
            temp.Add(right[0]);
            right.RemoveAt(0);
        }
    }
    if (left.Count > 0) {
        for (int i = 0; i < left.Count; i++)
            temp.Add(left[i]);
    }
    if (right.Count > 0) {
        for (int i = 0; i < right.Count; i++)
            temp.Add(right[i]);
    }
    return temp;
}

Leave a Comment

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