迭代合并排序

// Recursive C++ program for merge sort

#include<bits/stdc++.h>

using namespace std;

// Function to merge the two haves

// arr[l..m] and arr[m+1..r] of array arr[]

void merge( int arr[], int l, int m, int r);

// l is for left index and r is

// right index of the sub-array

// of arr to be sorted

void mergeSort( int arr[], int l, int r)

{

if (l < r)

{

// Same as (l+r)/2 but avoids

// overflow for large l & h

int m = l + (r - l) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

}

}

// Function to merge the two haves arr[l..m]

// and arr[m+1..r] of array arr[]

void merge( int arr[], int l, int m, int r)

{

int k;

int n1 = m - l + 1;

int n2 =  r - m;

// Create temp arrays

int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]

for ( int i = 0; i < n1; i++)

L[i] = arr[l + i];

for ( int j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

// Merge the temp arrays

// back into arr[l..r]

int i = 0;

int j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

// Copy the remaining elements

// of L[], if there are any

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

// Copy the remaining elements

// of R[], if there are any

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

// Function to print an array

void printArray( int A[], int size)

{

for ( int i = 0; i < size; i++)

printf ( "%d " , A[i]);

cout << "" ;

}

// Driver code

int main()

{

int arr[] = { 12, 11, 13, 5, 6, 7 };

int arr_size = sizeof (arr) / sizeof (arr[0]);

cout << "Given array is " ;

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "Sorted array is " ;

printArray(arr, arr_size);

return 0;

}

// This code is contributed by Mayank Tyagi

/* Recursive C program for merge sort */

#include<stdlib.h>

#include<stdio.h>

/* Function to merge the two haves

arr[l..m] and arr[m+1..r] of array arr[] */

void merge( int arr[], int l, int m, int r);

/* l is for left index and r is

right index of the sub-array

of arr to be sorted */

void mergeSort( int arr[], int l, int r)

{

if (l < r)

{

// Same as (l+r)/2 but avoids

// overflow for large l & h

int m = l+(r-l)/2;

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

/* Function to merge the two haves arr[l..m]

and arr[m+1..r] of array arr[] */

void merge( int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 =  r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements

of L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements

of R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

void printArray( int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf ( "%d " , A[i]);

printf ( "" );

}

/* Driver program to test above functions */

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof (arr)/ sizeof (arr[0]);

printf ( "Given array is " );

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf ( "Sorted array is " );

printArray(arr, arr_size);

return 0;

}

// Recursive Java Program for merge sort

import java.util.Arrays;

public class GFG

{

public static void mergeSort( int [] array)

{

if (array == null )

{

return ;

}

if (array.length > 1 )

{

int mid = array.length / 2 ;

// Split left part

int [] left = new int [mid];

for ( int i = 0 ; i < mid; i++)

{

left[i] = array[i];

}

// Split right part

int [] right = new int [array.length - mid];

for ( int i = mid; i < array.length; i++)

{

right[i - mid] = array[i];

}

mergeSort(left);

mergeSort(right);

int i = 0 ;

int j = 0 ;

int k = 0 ;

// Merge left and right arrays

while (i < left.length && j < right.length)

{

if (left[i] < right[j])

{

array[k] = left[i];

i++;

}

else

{

array[k] = right[j];

j++;

}

k++;

}

// Collect remaining elements

while (i < left.length)

{

array[k] = left[i];

i++;

k++;

}

while (j < right.length)

{

array[k] = right[j];

j++;

k++;

}

}

}

// Driver program to test above functions.

public static void main(String[] args)

{

int arr[] = { 12 , 11 , 13 , 5 , 6 , 7 };

int i= 0 ;

System.out.println( "Given array is" );

for (i= 0 ; i<arr.length; i++)

System.out.print(arr[i]+ " " );

mergeSort(arr);

System.out.println( "" );

System.out.println( "Sorted array is" );

for (i= 0 ; i<arr.length; i++)

System.out.print(arr[i]+ " " );

}

}

// Code Contributed by Mohit Gupta_OMG

# Recursive Python Program for merge sort

def merge(left, right):

if not len (left) or not len (right):

return left or right

result = []

i, j = 0 , 0

while ( len (result) < len (left) + len (right)):

if left[i] < right[j]:

result.append(left[i])

i + = 1

else :

result.append(right[j])

j + = 1

if i = = len (left) or j = = len (right):

result.extend(left[i:] or right[j:])

break

return result

def mergesort( list ):

if len ( list ) < 2 :

return list

middle = int ( len ( list ) / 2 )

left = mergesort( list [:middle])

right = mergesort( list [middle:])

return merge(left, right)

seq = [ 12 , 11 , 13 , 5 , 6 , 7 ]

print ( "Given array is" )

print (seq);

print ( "" )

print ( "Sorted array is" )

print (mergesort(seq))

# Code Contributed by Mohit Gupta_OMG

/* Iterative C# program for merge

sort */

using System;

class GFG {

/* l is for left index and r

is right index of the sub-array

of arr to be sorted */

static void mergeSort( int [] arr,

int l, int r)

{

if (l < r)

{

// Same as (l+r)/2 but avoids

// overflow for large l & h

int m = l + (r - l) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

/* Function to merge the two haves

arr[l..m] and arr[m+1..r] of array

arr[] */

static void merge( int [] arr, int l,

int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int []L = new int [n1];

int []R = new int [n2];

/* Copy data to temp arrays

L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back

into arr[l..r]*/

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of

L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of

R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

static void printArray( int []A, int size)

{

int i;

for (i=0; i < size; i++)

Console.Write(A[i]+ " " );

Console.Write( "" );

}

/* Driver program to test above functions */

public static void Main()

{

int []arr = {12, 11, 13, 5, 6, 7};

int arr_size = arr.Length;

Console.Write( "Given array is " );

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

Console.Write( "Sorted array is " );

printArray(arr, arr_size);

}

}

// This code is contributed by Smitha

<script>

// Recursive javascript Program for merge sort

function mergeSort(array) {

if (array == null ) {

return ;

}

if (array.length > 1) {

var mid = parseInt(array.length / 2);

// Split left part

var left = Array(mid).fill(0);

for (i = 0; i < mid; i++) {

left[i] = array[i];

}

// Split right part

var right = Array(array.length - mid).fill(0);

for (i = mid; i < array.length; i++) {

right[i - mid] = array[i];

}

mergeSort(left);

mergeSort(right);

var i = 0;

var j = 0;

var k = 0;

// Merge left and right arrays

while (i < left.length && j < right.length) {

if (left[i] < right[j]) {

array[k] = left[i];

i++;

} else {

array[k] = right[j];

j++;

}

k++;

}

// Collect remaining elements

while (i < left.length) {

array[k] = left[i];

i++;

k++;

}

while (j < right.length) {

array[k] = right[j];

j++;

k++;

}

}

}

// Driver program to test above functions.

var arr = [ 12, 11, 13, 5, 6, 7 ];

var i = 0;

document.write( "Given array is<br/>" );

for (i = 0; i < arr.length; i++)

document.write(arr[i] + " " );

mergeSort(arr);

document.write( "<br/><br/>" );

document.write( "Sorted array is<br/>" );

for (i = 0; i < arr.length; i++)

document.write(arr[i] + " " );

// This code is contributed by umadevi9616

</script>

/* Iterative C program for merge sort */

#include <bits/stdc++.h>

using namespace std;

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

void merge( int arr[], int l, int m, int r);

// Utility function to find minimum of two integers

int min( int x, int y) { return (x<y)? x :y; }

/* Iterative mergesort function to sort arr[0...n-1] */

void mergeSort( int arr[], int n)

{

int curr_size; // For current size of subarrays to be merged

// curr_size varies from 1 to n/2

int left_start; // For picking starting index of left subarray

// to be merged

// Merge subarrays in bottom up manner.  First merge subarrays of

// size 1 to create sorted subarrays of size 2, then merge subarrays

// of size 2 to create sorted subarrays of size 4, and so on.

for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)

{

// Pick starting point of different subarrays of current size

for (left_start=0; left_start<n-1; left_start += 2*curr_size)

{

// Find ending point of left subarray. mid+1 is starting

// point of right

int mid = min(left_start + curr_size - 1, n-1);

int right_end = min(left_start + 2*curr_size - 1, n-1);

// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]

merge(arr, left_start, mid, right_end);

}

}

}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

void merge( int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 =  r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

void printArray( int A[], int size)

{

int i;

for (i=0; i < size; i++)

cout << " " << A[i];

cout << "" ;

}

/* Driver program to test above functions */

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof (arr)/ sizeof (arr[0]);

cout << "Given array is " ;

printArray(arr, n);

mergeSort(arr, n);

cout << "Sorted array is " ;

printArray(arr, n);

return 0;

}

// This code is contributed shivanisinghss2110

/* Iterative C program for merge sort */

#include<stdlib.h>

#include<stdio.h>

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

void merge( int arr[], int l, int m, int r);

// Utility function to find minimum of two integers

int min( int x, int y) { return (x<y)? x :y; }

/* Iterative mergesort function to sort arr[0...n-1] */

void mergeSort( int arr[], int n)

{

int curr_size; // For current size of subarrays to be merged

// curr_size varies from 1 to n/2

int left_start; // For picking starting index of left subarray

// to be merged

// Merge subarrays in bottom up manner.  First merge subarrays of

// size 1 to create sorted subarrays of size 2, then merge subarrays

// of size 2 to create sorted subarrays of size 4, and so on.

for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)

{

// Pick starting point of different subarrays of current size

for (left_start=0; left_start<n-1; left_start += 2*curr_size)

{

// Find ending point of left subarray. mid+1 is starting

// point of right

int mid = min(left_start + curr_size - 1, n-1);

int right_end = min(left_start + 2*curr_size - 1, n-1);

// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]

merge(arr, left_start, mid, right_end);

}

}

}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

void merge( int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 =  r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

void printArray( int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf ( "%d " , A[i]);

printf ( "" );

}

/* Driver program to test above functions */

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof (arr)/ sizeof (arr[0]);

printf ( "Given array is " );

printArray(arr, n);

mergeSort(arr, n);

printf ( "Sorted array is " );

printArray(arr, n);

return 0;

}

/* Iterative Java program for merge sort */

import java.lang.Math.*;

class GFG {

/* Iterative mergesort function to sor

t arr[0...n-1] */

static void mergeSort( int arr[], int n)

{

// For current size of subarrays to

// be merged curr_size varies from

// 1 to n/2

int curr_size;

// For picking starting index of

// left subarray to be merged

int left_start;

// Merge subarrays in bottom up

// manner. First merge subarrays

// of size 1 to create sorted

// subarrays of size 2, then merge

// subarrays of size 2 to create

// sorted subarrays of size 4, and

// so on.

for (curr_size = 1 ; curr_size <= n- 1 ;

curr_size = 2 *curr_size)

{

// Pick starting point of different

// subarrays of current size

for (left_start = 0 ; left_start < n- 1 ;

left_start += 2 *curr_size)

{

// Find ending point of left

// subarray. mid+1 is starting

// point of right

int mid = Math.min(left_start + curr_size - 1 , n- 1 );

int right_end = Math.min(left_start

+ 2 *curr_size - 1 , n- 1 );

// Merge Subarrays arr[left_start...mid]

// & arr[mid+1...right_end]

merge(arr, left_start, mid, right_end);

}

}

}

/* Function to merge the two haves arr[l..m] and

arr[m+1..r] of array arr[] */

static void merge( int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1 ;

int n2 = r - m;

/* create temp arrays */

int L[] = new int [n1];

int R[] = new int [n2];

/* Copy data to temp arrays L[]

and R[] */

for (i = 0 ; i < n1; i++)

L[i] = arr[l + i];

for (j = 0 ; j < n2; j++)

R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into

arr[l..r]*/

i = 0 ;

j = 0 ;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of

L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of

R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

static void printArray( int A[], int size)

{

int i;

for (i= 0 ; i < size; i++)

System.out.printf( "%d " , A[i]);

System.out.printf( "" );

}

/* Driver program to test above functions */

public static void main(String[] args)

{

int arr[] = { 12 , 11 , 13 , 5 , 6 , 7 };

int n = arr.length;

System.out.printf( "Given array is " );

printArray(arr, n);

mergeSort(arr, n);

System.out.printf( "Sorted array is " );

printArray(arr, n);

}

}

// This code is contributed by Smitha

# Iterative Merge sort (Bottom Up)

# Iterative mergesort function to

# sort arr[0...n-1]

# perform bottom up merge

def mergeSort(a):

# start with least partition size of 2^0 = 1

width = 1

n = len (a)

# subarray size grows by powers of 2

# since growth of loop condition is exponential,

# time consumed is logarithmic (log2n)

while (width < n):

# always start from leftmost

l = 0 ;

while (l < n):

r = min (l + (width * 2 - 1 ), n - 1 )

m = min (l + width - 1 ,n - 1 )

# final merge should consider

# unmerged sublist if input arr

# size is not power of 2

merge(a, l, m, r)

l + = width * 2

# Increasing sub array size by powers of 2

width * = 2

return a

# Merge Function

def merge(a, l, m, r):

n1 = m - l + 1

n2 = r - m

L = [ 0 ] * n1

R = [ 0 ] * n2

for i in range ( 0 , n1):

L[i] = a[l + i]

for i in range ( 0 , n2):

R[i] = a[m + i + 1 ]

i, j, k = 0 , 0 , l

while i < n1 and j < n2:

if L[i] < = R[j]:

a[k] = L[i]

i + = 1

else :

a[k] = R[j]

j + = 1

k + = 1

while i < n1:

a[k] = L[i]

i + = 1

k + = 1

while j < n2:

a[k] = R[j]

j + = 1

k + = 1

# Driver code

a = [ - 74 , 48 , - 20 , 2 , 10 , - 84 , - 5 , - 9 , 11 , - 24 , - 91 , 2 , - 71 , 64 , 63 , 80 , 28 , - 30 , - 58 , - 11 , - 44 , - 87 , - 22 , 54 , - 74 , - 10 , - 55 , - 28 , - 46 , 29 , 10 , 50 , - 72 , 34 , 26 , 25 , 8 , 51 , 13 , 30 , 35 , - 8 , 50 , 65 , - 6 , 16 , - 2 , 21 , - 78 , 35 , - 13 , 14 , 23 , - 3 , 26 , - 90 , 86 , 25 , - 56 , 91 , - 13 , 92 , - 25 , 37 , 57 , - 20 , - 69 , 98 , 95 , 45 , 47 , 29 , 86 , - 28 , 73 , - 44 , - 46 , 65 , - 84 , - 96 , - 24 , - 12 , 72 , - 68 , 93 , 57 , 92 , 52 , - 45 , - 2 , 85 , - 63 , 56 , 55 , 12 , - 85 , 77 , - 39 ]

print ( "Given array is " )

print (a)

mergeSort(a)

print ( "Sorted array is " )

print (a)

# Contributed by Madhur Chhangani [RCOEM]

# corrected and improved by @mahee96

/* Iterative C# program for merge sort */

using System;

public class GFG {

/* Iterative mergesort function to sor

t arr[0...n-1] */

static void mergeSort( int []arr, int n)

{

// For current size of subarrays to

// be merged curr_size varies from

// 1 to n/2

int curr_size;

// For picking starting index of

// left subarray to be merged

int left_start;

// Merge subarrays in bottom up

// manner. First merge subarrays

// of size 1 to create sorted

// subarrays of size 2, then merge

// subarrays of size 2 to create

// sorted subarrays of size 4, and

// so on.

for (curr_size = 1; curr_size <= n-1;

curr_size = 2*curr_size)

{

// Pick starting point of different

// subarrays of current size

for (left_start = 0; left_start < n-1;

left_start += 2*curr_size)

{

// Find ending point of left

// subarray. mid+1 is starting

// point of right

int mid = Math.Min(left_start + curr_size - 1,n-1);

int right_end = Math.Min(left_start

+ 2*curr_size - 1, n-1);

// Merge Subarrays arr[left_start...mid]

// & arr[mid+1...right_end]

merge(arr, left_start, mid, right_end);

}

}

}

/* Function to merge the two haves arr[l..m] and

arr[m+1..r] of array arr[] */

static void merge( int []arr, int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int []L = new int [n1];

int []R = new int [n2];

/* Copy data to temp arrays L[]

and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into

arr[l..r]*/

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of

L[], if there are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of

R[], if there are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

static void printArray( int []A, int size)

{

int i;

for (i=0; i < size; i++)

Console.Write(A[i]+ " " );

Console.WriteLine( "" );

}

/* Driver program to test above functions */

public static void Main()

{

int []arr = {-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39};

int n = arr.Length;

Console.Write( "Given array is " );

printArray(arr, n);

mergeSort(arr, n);

Console.Write( "Sorted array is " );

printArray(arr, n);

}

}

// This code is contributed by Rajput-Ji

<script>

/* Iterative javascript program for merge sort */

/*

* Iterative mergesort function to sor t arr[0...n-1]

*/

function mergeSort(arr , n) {

// For current size of subarrays to

// be merged curr_size varies from

// 1 to n/2

var curr_size;

// For picking starting index of

// left subarray to be merged

var left_start;

// Merge subarrays in bottom up

// manner. First merge subarrays

// of size 1 to create sorted

// subarrays of size 2, then merge

// subarrays of size 2 to create

// sorted subarrays of size 4, and

// so on.

for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {

// Pick starting point of different

// subarrays of current size

for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {

// Find ending point of left

// subarray. mid+1 is starting

// point of right

var mid = Math.min(left_start + curr_size - 1, n - 1);

var right_end = Math.min(left_start + 2 * curr_size - 1, n - 1);

// Merge Subarrays arr[left_start...mid]

// & arr[mid+1...right_end]

merge(arr, left_start, mid, right_end);

}

}

}

/*

* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr

*/

function merge(arr , l , m , r) {

var i, j, k;

var n1 = m - l + 1;

var n2 = r - m;

/* create temp arrays */

var L = Array(n1).fill(0);

var R = Array(n2).fill(0);

/*

* Copy data to temp arrays L and R

*/

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1 + j];

/*

* Merge the temp arrays back into arr[l..r]

*/

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

}

k++;

}

/*

* Copy the remaining elements of L, if there are any

*/

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

/*

* Copy the remaining elements of R, if there are any

*/

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}

}

/* Function to print an array */

function printArray(A , size) {

var i;

for (i = 0; i < size; i++)

document.write( A[i]+ " " );

document.write( "<br/>" );

}

/* Driver program to test above functions */

var arr = [-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39];

var n = arr.length;

document.write( "Given array is <br/>" );

printArray(arr, n);

mergeSort(arr, n);

document.write( "<br/>Sorted array is <br/>" );

printArray(arr, n);

// This code contributed by umadevi9616

</script>