Merge sort är en sorteringsalgoritm baserad på “dela och härska”-tekniken. Det är en av de mest effektiva sorteringsalgoritmerna.
I den här artikeln kommer du att lära dig hur sammanslagningssorteringsalgoritmen fungerar, sammanslagningssorteringsalgoritmen, dess komplexitet i tid och rum och dess implementering i olika programmeringsspråk som C++, Python och JavaScript.
Hur fungerar sammanslagningssorteringsalgoritmen?
Merge sort fungerar på principen om dela och erövra. Merge sort bryter upprepade gånger ner en array i två lika stora subarrays tills varje subarray består av ett enda element. Slutligen slås alla dessa undermatriser samman så att den resulterande matrisen sorteras.
Detta koncept kan förklaras mer effektivt med hjälp av ett exempel. Tänk på en osorterad array med följande element: {16, 12, 15, 13, 19, 17, 11, 18}.
Här delar sammanslagningssorteringsalgoritmen upp arrayen i två halvor, kallar sig för de två halvorna och slår sedan samman de två sorterade halvorna.
Slå samman sorteringsalgoritm
Nedan är algoritmen för sammanslagningssorten:
MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)
Tid och rumskomplexitet för sammanslagningssorteringsalgoritmen
Sorteringsalgoritmen Merge kan uttryckas i form av följande återkommande relation:
T(n) = 2T(n/2) + O(n)
Efter att ha löst detta återkommande förhållande med hjälp av mastersatsen eller återfallsträdmetoden får du lösningen som O(n logn). Sålunda är tidskomplexiteten för sammanslagningssorteringsalgoritmen O(n logn).
Den bästa möjliga tidskomplexiteten för sammanslagningssorten: O(n logn)
Den genomsnittliga tidskomplexiteten för sammanslagningssorten: O(n logn)
Det värsta tänkbara tidskomplexiteten för sammanslagningssorten: O(n logn)
Hjälputrymmets komplexitet av sammanslagningssortsalgoritmen är På) som n extra utrymme krävs i implementeringen av merge sort.
C++ Implementering av Merge Sort Algorithm
Nedan är C++-implementeringen av sammanslagningssorteringsalgoritmen:
// C++ implementation of the
// merge sort algorithm
#include <iostream>
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i < leftSubarraySize; i++)
L[i] = arr[leftIndex + i];
for (int j = 0; j < rightSubarraySize; j++)
R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array:" << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << "Sorted array:" << endl;
printArray(arr, size);
return 0;
}
Produktion:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19
JavaScript-implementering av Merge Sort Algorithm
Nedan är JavaScript-implementeringen av sammanslagningssorteringsalgoritmen:
// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i<leftSubarraySize; i++) {
L[i] = arr[leftIndex + i];
}
for (let j = 0; j<rightSubarraySize; j++) {
R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i<size; i++) {
document.write(arr[i] + " ");
}
document.write("<br>");
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write("Unsorted array:<br>");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write("Sorted array:<br>");
printArray(arr, size);
Produktion:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19
Python-implementering av Merge Sort Algorithm
Nedan är Python-implementeringen av sammanslagningssorteringsalgoritmen:
# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i < len(L):
arr[k] = L[i]
i = i + 1
k = k + 1
while j < len(R):
arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=" ")
print()# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print("Unsorted array:")
printArray(arr, size)
mergeSort(arr)
print("Sorted array:")
printArray(arr, size)
Produktion:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19
Förstå andra sorteringsalgoritmer
Sortering är en av de mest använda algoritmerna inom programmering. Du kan sortera element i olika programmeringsspråk med hjälp av olika sorteringsalgoritmer som snabbsortering, bubbelsortering, sammanslagningssortering, infogningssortering, etc.
Bubblesortering är det bästa valet om du vill lära dig om den enklaste sorteringsalgoritmen.
Om författaren
Yuvraj Chandra (80 artiklar publicerade)
Yuvraj är en datavetenskapsstudent vid University of Delhi, Indien. Han brinner för Full Stack Web Development. När han inte skriver undersöker han djupet i olika teknologier.
Mer från Yuvraj Chandra
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
