Serwis Edukacyjny
Nauczycieli

w I-LO w Tarnowie
obrazek Materiały głownie dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2026 mgr Jerzy Wałaszek

Sortowanie przez scalanie
  Merge Sort

SPIS TREŚCI
Podrozdziały

Algorytm

Poczynając od tego rozdziału przechodzimy do opisu algorytmów szybkich, tzn. takich, które posiadają klasę czasowej złożoności obliczeniowej równą O(n·log n) lub nawet lepszą.

W informatyce zwykle obowiązuje zasada, iż prosty algorytm posiada dużą złożoność obliczeniową, natomiast algorytm zaawansowany posiada małą złożoność obliczeniową, ponieważ wykorzystuje on pewne własności, dzięki którym szybciej dochodzi do rozwiązania.

Wiele dobrych algorytmów sortujących korzysta z rekurencji, która powstaje wtedy, gdy do rozwiązania problemu algorytm wykorzystuje samego siebie ze zmienionym zestawem danych.

Przykład:

Jako przykład może posłużyć rekurencyjne obliczanie silni. Silnię liczby n należącej do zbioru liczb naturalnych definiujemy następująco:

n! = 1 × 2 × 3 × ... × (n - 1) × n

Na przykład:

5! = 1 × 2 × 3 × 4 × 5 = 120

Rekurencyjne obliczanie  silni

Specyfikacja algorytmu

Dane wejściowe

n - liczba, której silnie liczymy na danym poziomie rekurencyjnym,  n ∈ N

Dane wyjściowe

Wartość silni n!

Lista kroków

K01: Jeśli n < 2,
to silnia(n) ← 1
i zakończ
K02: silnia(n) ← n × silnia(n - 1)
i zakończ

Przykładowy program

C++
// Rekurencyjne obliczanie silni
//------------------------------
// (C)2026 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

unsigned long long silnia(int n)
{
  if(n < 2)
    return 1;
  else
    return n * silnia(n - 1);
}

// Program główny
//---------------

int main()
{
  int n;

  cout << "Program oblicza rekurencyjnie silnie z liczby n\n"
          "-----------------------------------------------\n"
          "  (C)2026 mgr Jerzy Walaszek  I LO w Tarnowie\n\n"
          "n (od 1 do 20) = "; cin >> n;
  cout << endl << n << "! = " << silnia(n)
       << endl << endl
       << "Nacisnij Enter...";
  system("pause");
  return 0;
}
Pascal
// Rekurencyjne obliczanie silni
//------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I LO w Tarnowie

program silnia_rek;

function silnia(n : cardinal) : qword;
begin
  if n < 2 then
    silnia := 1
  else
    silnia := n * silnia(n - 1);
end;

var
  n : cardinal;

begin
  writeln('Program oblicza rekurencyjnie silnie z liczby n');
  writeln('-----------------------------------------------');
  writeln('  (C)2005 mgr Jerzy Walaszek  I LO w Tarnowie');
  writeln;
  write('n (od 1 do 20) = '); readln(n);
  writeln;
  writeln(n,'! = ',silnia(n));
  writeln;
  write('Nacisnij Enter...'); readln;
end.
Basic
' Rekurencyjne obliczanie silni
'------------------------------
' (C)2026 mgr Jerzy Wałaszek
' I LO w Tarnowie

FUNCTION silnia(n AS INTEGER) AS ULONGINT
  IF n < 2 THEN
    RETURN 1
  ELSE
    RETURN n * silnia(n - 1)
  END IF
END FUNCTION

' Program główny
'---------------

DIM AS INTEGER n

PRINT "Silnia z n"
PRINT "----------"
PRINT "(C)2026 mgr Jerzy Walaszek"
PRINT
INPUT "n (od 1 do 20) = "; n
PRINT
PRINT n; "! = "; silnia(n)
PRINT
PRINT
PRINT "Nacisnij Enter..."
SLEEP
END
Python (dodatek)
# Rekurencyjne obliczanie silni
#------------------------------
# (C)2026 mgr Jerzy Wałaszek
# I LO w Tarnowie

def silnia(n):
    if n < 2:
        return 1
    else:
        return n * silnia(n - 1)

# Program główny
#---------------

print("Program oblicza rekurencyjnie silnię z liczby n")
print("-----------------------------------------------")
print("          (C)2026 mgr Jerzy Wałaszek")
print()
n = int(input("n = "))
print()
print(n,"! = ",silnia(n),sep="")
print()
print()
input("Naciśnij Enter...")
Wynik:
 Program oblicza rekurencyjnie silnię z liczby n
-----------------------------------------------
          (C)2026 mgr Jerzy Wałaszek

n = 20

20! = 2432902008176640000


Naciśnij Enter...

Dzięki rekurencji funkcja wyliczająca wartość silni staje się niezwykle prosta. Najpierw sprawdzamy warunek zakończenia rekurencji, tzn. sytuację, gdy wynik dla otrzymanego zestawu danych jest oczywisty. W przypadku silni sytuacja taka wystąpi dla n < 2 - silnia ma wartość 1. Jeśli warunek zakończania rekurencji nie wystąpi, to wartość wyznaczamy za pomocą rekurencyjnego wywołania obliczania silni dla argumentu zmniejszonego o 1. Wynik tego wywołania mnożymy przez n i zwracamy jako wartość silni dla n.

Silnia rośnie bardzo szybko. Z tego powodu nasz program wylicza wartość silni tylko dla liczb całkowitych do 20. Silnia 21! wykracza już poza zakres liczb całkowitych 64-bitowych. Ograniczenie to nie dotyczy języka Python, który stosuje duże liczby całkowite.

obrazek

Wynaleziony w 1945 roku przez Johna von Neumanna algorytm sortowania przez scalanie jest algorytmem rekurencyjnym. Wykorzystuje zasadę dziel i zwyciężaj (ang. divide and conquer), która polega na podziale zadania głównego na zadania mniejsze dotąd, aż rozwiązanie stanie się oczywiste. Algorytm sortujący dzieli porządkowany zbiór na kolejne połowy dopóki taki podział jest możliwy (tzn. podzbiór zawiera co najmniej dwa elementy). Następnie uzyskane w ten sposób części zbioru rekurencyjnie sortuje tym samym algorytmem. Posortowane części łączy ze sobą za pomocą scalania, tak aby wynikowy zbiór był posortowany.


do podrozdziału  do strony 

Scalanie zbiorów uporządkowanych

Podstawową operacją algorytmu jest scalanie dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany. Operację scalania realizujemy wykorzystując pomocniczy zbiór, w którym będziemy tymczasowo odkładać scalane elementy dwóch zbiorów. Ogólna zasada jest następująca:

  1. Przygotuj pusty zbiór tymczasowy

  2. Dopóki żaden ze scalanych zbiorów nie jest pusty, porównuj ze sobą pierwsze elementy każdego z nich i w zbiorze tymczasowym umieszczaj mniejszy z elementów usuwając go jednocześnie ze scalanego zbioru.

  3. W zbiorze tymczasowym umieść zawartość tego scalanego zbioru, który zawiera jeszcze elementy.

  4. Zawartość zbioru tymczasowego przepisz do zbioru wynikowego i zakończ algorytm.

Przykład:

Połączmy za pomocą opisanego algorytmu dwa uporządkowane zbiory: { 1 3 6 7 9 } z { 2 3 4 6 8 }

Scalane
zbiory
Zbiór
tymczasowy
Opis wykonywanych działań
[1] 3  6  7  9 
 2  3  4  6  8 
 
Porównujemy ze sobą najmniejsze elementy
scalanych zbiorów. Ponieważ zbiory te są już
uporządkowane, to najmniejszymi
elementami będą zawsze ich pierwsze
elementy.
    3  6  7  9 
 2  3  4  6  8 
[1]
W zbiorze tymczasowym umieszczamy
mniejszy element, w tym przypadku będzie to
liczba 1. Jednocześnie element ten zostaje
usunięty z pierwszego zbioru
    3  6  7  9 
[2]  4  6  8 
 1 
Porównujemy kolejne dwa elementy
i mniejszy umieszczamy w zbiorze
tymczasowym.
   [3] 6  7  9 
    3   6  8 
 1[2]
Następne porównanie i w zbiorze
tymczasowym umieszczamy liczbę 3.
Ponieważ są to elementy równe, to nie ma
znaczenia, z którego zbioru weźmiemy
element 3.
       6  7  9 
   [3] 4  6  8 
 1 2[3]
Teraz do zbioru tymczasowego trafi drugie 3.
       6  7  
      [4] 6  8 
 1 2 3[3]
W zbiorze tymczasowym umieszczamy
mniejszy z porównywanych elementów, czyli
liczbę 4.
      [6] 7  9 
          6  8 
 1 2 3 3[4]
Porównywane elementy są równe, zatem
w zbiorze tymczasowym umieszczamy
dowolny z nich.
          7  
         [6] 8 
 1 2 3 3 4[6]
Teraz drugą liczbę 6.
         [7] 
             8 
 1 2 3 3 4 6[6]
W zbiorze tymczasowym umieszczamy
liczbę 7
             9 
            [8]
 1 2 3 3 4 6 6[7]
Teraz 8
            [9]
 1 2 3 3 4 6 6 7[8]
Drugi zbiór jest pusty. Od tego momentu już
nie porównujemy, lecz wprowadzamy do
zbioru tymczasowego wszystkie pozostałe
elementy pierwszego zbioru, w tym przypadku
będzie to liczba 9.
 
 1 2 3 3 4 6 6 7 8[9]
Koniec scalania. Zbiór tymczasowy zawiera
wszystkie elementy scalanych zbiorów i jest
uporządkowany. Możemy w dalszej kolejności
przepisać jego zawartość do zbioru
docelowego.

Z podanego przykładu możemy wyciągnąć wniosek, iż operacja scalania dwóch uporządkowanych zbiorów jest dosyć prosta. Diabeł jak zwykle tkwi w szczegółach.


do podrozdziału  do strony 

Algorytm scalania dwóch zbiorów

Przed przystąpieniem do wyjaśniania sposobu łączenia dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany musimy zastanowić się nad sposobem reprezentacji danych. Przyjmijmy, iż elementy zbioru będą przechowywane w jednej tablicy, którą oznaczymy literką d. Każdy element w tej tablicy będzie posiadał swój numer, czyli indeks z zakresu od 1 do n.

Kolejnym zagadnieniem jest sposób reprezentacji scalanych zbiorów. W przypadku algorytmu sortowania przez scalanie zawsze będą to dwie przyległe połówki zbioru, który został przez ten algorytm podzielony. Co więcej, wynik scalenia ma być umieszczony z powrotem w tym samym zbiorze.

Przykład:

Prześledźmy prosty przykład. Mamy posortować zbiór o postaci: { 6 5 4 1 3 7 9 2 }

Sortowany zbiór Opis wykonywanych operacji
d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8]
6 5 4 1 3 7 9 2 Zbiór wyjściowy.
6 5  4 1 3 7 9 2 Pierwszy podział.
6 5 4 1 3 7 9 2 Drugi podział
6 5 4 1 3 7 9 2 Trzeci podział.
5 6 1 4 3 7 2 9 Pierwsze scalanie.
1
4 5 6 2 3 7 9 Drugie scalanie.
1 2 3 4 5 6 7 9 Trzecie scalanie. Koniec.

Ponieważ w opisywanym tutaj algorytmie sortującym scalane podzbiory są przyległymi do siebie częściami innego zbioru, zatem logiczne będzie użycie do ich definicji indeksów wybranych elementów tych podzbiorów:

ip - indeks pierwszego elementu w młodszym podzbiorze
is - indeks pierwszego elementu w starszym podzbiorze
ik - indeks ostatniego elementu w starszym podzbiorze

Przez podzbiór młodszy rozumiemy podzbiór zawierający elementy o indeksach mniejszych niż indeksy elementów w podzbiorze starszym.

pozostała część zbioru ip ... is ... ik pozostała część zbioru

młodszy podzbiór

starszy podzbiór

Indeks końcowego elementu młodszej połówki zbioru z łatwością wyliczamy - będzie on o 1 mniejszy od indeksu pierwszego elementu starszej połówki.

Przykład:

Po pierwszym podziale prezentowanego powyżej zbioru otrzymujemy następujące wartości indeksów:
Młodsza
połówka
Starsza
połówka
ip = 1 is = 5
ik = 8
Po kolejnym podziale połówek otrzymujemy 4 ćwiartki dwuelementowe. Wartości indeksów będą następujące:
Młodsza połówka Starsza połówka
Młodsza
ćwiartka
Starsza
ćwiartka
Młodsza
ćwiartka
Starsza
ćwiartka
ip = 1 is = 3 ip = 5 is = 7
ik = 4 ik = 8

Specyfikacja algorytmu scalania

Scalaj(ip, is, ik)

Dane wejściowe

d[ ] - scalany zbiór
ip - indeks pierwszego elementu w młodszym podzbiorze,  ip ∈ N
is - indeks pierwszego elementu w starszym podzbiorze,  is ∈ N
ik - indeks ostatniego elementu w starszym podzbiorze,  ik ∈ N

Dane wyjściowe

d[ ] - scalony zbiór

Zmienne pomocnicze

p[ ] - zbiór pomocniczy, który zawiera tyle samo elementów, co zbiór d[ ].
i1 - indeks elementów w młodszej połówce zbioru d[ ],  i1 ∈ N
i2 - indeks elementów w starszej połówce zbioru d[ ],  i2 ∈ N
i - indeks elementów w zbiorze pomocniczym p[ ],  i ∈ N

Lista kroków algorytmu scalania

K01: i1 ← ip;   i2 ← is;   i ← ip
K02: Dla i = ip, ip + 1, ..., ik:
    jeśli (i1 = is) ∨ (i2 ≤ ik  i d[i1] > d[i2]),
    to p[i] ← d[i2];   i2 ← i2 + 1
    inaczej p[i] ← d[i1];   i1 ← i1 + 1
K03: Dla i = ip, ip + 1,...,ik:
    d[i] ← p[i]
K04: Zakończ

Schemat blokowy algorytmu scalania

obrazek

Operacja scalania dwóch podzbiorów wymaga dodatkowej pamięci o rozmiarze równym sumie rozmiarów scalanych podzbiorów. Dla prostoty na potrzeby naszego algorytmu zarezerwujemy tablicę p o rozmiarze równym rozmiarowi zbioru d[ ]. W tablicy p algorytm będzie tworzył zbiór tymczasowy, który po zakończeniu scalania zostanie przepisany do zbioru d[ ] w miejsce dwóch scalanych podzbiorów.

Parametrami wejściowymi do algorytmu są indeksy ip, is oraz ik, które jednoznacznie definiują położenie dwóch podzbiorów do scalenia w obrębie tablicy d[ ]. Elementy tych podzbiorów będą indeksowane za pomocą zmiennych i1 (młodszy podzbiór od pozycji ip do is - 1) oraz i2 (starszy podzbiór od pozycji is do ik). Na początku algorytmu przypisujemy tym zmiennym indeksy pierwszych elementów w każdym podzbiorze.

Zmienna i będzie zawierała indeksy elementów wstawianych do tablicy p[ ]. Dla ułatwienia indeksy te przebiegają wartości od ip do ik, co odpowiada obszarowi tablicy d[ ] zajętemu przez dwa scalane podzbiory. Na początku do zmiennej i wprowadzamy indeks pierwszego elementu w tym obszarze, czyli ip.

Wewnątrz pętli sprawdzamy, czy indeksy i1 i i2 wskazują elementy podzbiorów. Jeśli któryś z nich wyszedł poza dopuszczalny zakres, to dany podzbiór jest wyczerpany - w takim przypadku do tablicy p przepisujemy elementy drugiego podzbioru.

Jeśli żaden z podzbiorów nie jest wyczerpany, porównujemy kolejne elementy z tych podzbiorów wg indeksów i1 i i2. Do tablicy p[ ] zapisujemy zawsze mniejszy z porównywanych elementów. Zapewnia to uporządkowanie elementów w tworzonym zbiorze wynikowym. Po zapisie elementu w tablicy p[ ], odpowiedni indeks i1 lub i2 jest zwiększany o 1. Zwiększany jest również indeks i, aby kolejny zapisywany element w tablicy p[ ] trafił na następne wolne miejsce. Pętla jest kontynuowana aż do zapełnienia w tablicy p[ ] obszaru o indeksach od ip do ik.

Wtedy przechodzimy do końcowej pętli, która przepisuje ten obszar z tablicy p[ ] do tablicy wynikowej d[ ]. Scalane zbiory zostają zapisane zbiorem wynikowym, który jest posortowany rosnąco.


do podrozdziału  do strony 

Opis algorytmu sortującego

Specyfikacja algorytmu sortującego

Sortuj(ip, ik)

Dane wejściowe

d[ ] - sortowany zbiór
ip - indeks pierwszego elementu w młodszym podzbiorze,  ip ∈ N
ik - indeks ostatniego elementu w starszym podzbiorze,  ik ∈ N

Dane wyjściowe

d[ ] - posortowany zbiór

Zmienne pomocnicze

is - indeks pierwszego elementu w starszym podzbiorze,  is ∈ N

Lista kroków algorytmu sortującego

K01: is ←  (ip + ik + 1) div 2
K02: Jeśli is - ip > 1, to Sortuj(ip, is - 1)
K03: Jeśli ik - is > 0, to Sortuj(is, ik)
K04: Scalaj(ip, is, ik)
K05: Zakończ

Schemat blokowy algorytmu sortującego

obrazek

Algorytm sortowania przez scalanie jest algorytmem rekurencyjnym. Wywołuje się go z zadanymi wartościami indeksów ip oraz ik. Przy pierwszym wywołaniu indeksy te powinny objąć cały zbiór d, zatem ip = 1, a ik = n.

Najpierw algorytm wyznacza indeks is, który wykorzystywany jest do podziału zbioru na dwie połówki:

Następnie sprawdzamy, czy dana połówka zbioru zawiera więcej niż jeden element. Jeśli tak, to rekurencyjnie sortujemy ją tym samym algorytmem.

Po posortowaniu obu połówek zbioru scalamy je za pomocą opisanej wcześniej procedury scalania podzbiorów uporządkowanych i kończymy algorytm. Zbiór jest posortowany.

W przykładowych programach procedurę scalania umieściliśmy bezpośrednio w kodzie algorytmu sortującego, aby zaoszczędzić na wywoływaniu.


do podrozdziału  do strony 

Przykładowe programy

C++
// Sortowanie przez scalanie
//--------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 20; // Liczebność zbioru.

int d[N],p[N];

// Procedura sortująca
//--------------------

void MergeSort(int i_p, int i_k)
{
  int i_s,i1,i2,i;

  i_s = (i_p + i_k + 1) / 2;
  if(i_s - i_p > 1)
    MergeSort(i_p, i_s - 1);
  if(i_k - i_s > 0)
    MergeSort(i_s, i_k);
  i1 = i_p; i2 = i_s;
  for(i = i_p; i <= i_k; i++)
    p[i] = ((i1 == i_s) ||
            ((i2 <= i_k) &&
             (d[i1] > d[i2])))
            ? d[i2++] : d[i1++];
  for(i = i_p; i <= i_k; i++)
    d[i] = p[i];
}

// Program główny
//---------------

int main()
{
  int i;

  cout << " Sortowanie przez scalanie\n"
          "---------------------------\n"
          "  (C)2005  Jerzy Walaszek\n\n"
          "Przed sortowaniem:\n\n";

// Najpierw wypełniamy tablicę d[]
// liczbami pseudolosowymi, a następnie
// wyświetlamy jej zawartość

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++)
    d[i] = rand() % 100;
  for(i = 0; i < N; i++)
    cout << setw(4) << d[i];
  cout << endl << endl;

// Sortujemy

  MergeSort(0,N-1);

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++)
    cout << setw(4) << d[i];
  cout << endl << endl;
  system("pause");
  return 0;
}
Pascal
// Sortowanie Przez Scalanie
//--------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

program Merge_Sort;

const N = 20; // Liczebność zbioru.

var
  d,p : array[1..N] of integer;

// Procedura sortująca
//--------------------
procedure MergeSort(i_p,i_k : integer);
var
  i_s,i1,i2,i : integer;
begin
  i_s := (i_p + i_k + 1) div 2;
  if i_s - i_p > 1 then
    MergeSort(i_p, i_s - 1);
  if i_k - i_s > 0 then
    MergeSort(i_s, i_k);
  i1 := i_p; i2 := i_s;
  for i := i_p to i_k do
    if (i1 = i_s) or
       ((i2 <= i_k) and
        (d[i1] > d[i2])) then
    begin
      p[i] := d[i2]; inc(i2);
    end
    else
    begin
      p[i] := d[i1]; inc(i1);
    end;
  for i := i_p to i_k do
    d[i] := p[i];
end;

// Program główny
//---------------

var
  i : integer;
begin
  writeln(' Sortowanie przez scalanie ');
  writeln('---------------------------');
  writeln('  (C)2005  Jerzy Walaszek  ');
  writeln;

// Najpierw wypełniamy tablicę d[]
// liczbami pseudolosowymi, a następnie
// wyświetlamy jej zawartość

  randomize;
  for i := 1 to N do
    d[i] := random(100);
  writeln('Przed sortowaniem:');
  writeln;
  for i := 1 to N do
    write(d[i] : 4);
  writeln;
  writeln;

// Sortujemy

  MergeSort(1,N);

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:');
  writeln;
  for i := 1 to N do
    write(d[i] : 4);
  writeln;
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.
Basic
' Sortowanie Przez Scalanie
'--------------------------
' (C)2012 Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie

CONST N = 20 ' Liczebność zbioru.

DIM SHARED d(1 TO N) AS INTEGER
DIM SHARED p(1 TO N) AS INTEGER

DECLARE SUB MergeSort(_
            BYVAL i_p AS INTEGER,_
            BYVAL i_k AS INTEGER)

DIM i AS INTEGER

PRINT " Sortowanie przez scalanie "
PRINT "---------------------------"
PRINT "  (C)2005  Jerzy Walaszek  "
PRINT

' Najpierw wypełniamy tablicę d()
' liczbami pseudolosowymi, a następnie
' wyświetlamy jej zawartość

RANDOMIZE TIMER
FOR i = 1 TO N
  d(i) = INT(RND * 100)
NEXT
PRINT "Przed sortowaniem:"
PRINT
FOR i = 1 TO N
  PRINT USING "####"; d(i);
NEXT
PRINT
PRINT

' Sortujemy

MergeSort 1, N

' Wyświetlamy wynik sortowania

PRINT "Po sortowaniu:"
PRINT
FOR i = 1 TO N
  PRINT USING "####"; d(i);
NEXT
PRINT
PRINT
PRINT "Nacisnij Enter..."
SLEEP
END

' Procedura sortująca
'--------------------
PUBLIC SUB MergeSort(_
           BYVAL i_p AS INTEGER,_
           BYVAL i_k AS INTEGER)

  DIM AS INTEGER i_s,i1,i2,i

  i_s = (i_p + i_k + 1) \ 2
  IF i_s - i_p > 1 THEN
    MergeSort i_p, i_s - 1
  END IF
  IF i_k - i_s > 0 THEN
    MergeSort i_s, i_k
  END IF
  i1 = i_p: i2 = i_s
  FOR i = i_p TO i_k
    IF (i1 = i_s) OR _
       ((i2 <= i_k) AND _
        (d(i1) > d(i2))) THEN
      p(i) = d(i2)
      i2 += 1
    ELSE
      p(i) = d(i1)
      i1 += 1
    END IF
  NEXT
  FOR i = i_p TO i_k
    d(i) = p(i)
  NEXT
END SUB
Python (dodatek)
# Sortowanie Przez Scalanie
#--------------------------
# (C)2026 Jerzy Wałaszek

import random

n = 20 # Liczebność zbioru.

d = [random.randrange(100) for i in range(n)]
p = [None] * n

# Procedura sortująca
#--------------------
def MergeSort(i_p,i_k):
    i_s = (i_p + i_k + 1) // 2
    if i_s - i_p > 1:
        MergeSort(i_p, i_s - 1)
    if i_k - i_s > 0:
        MergeSort(i_s, i_k)
    i1 = i_p
    i2 = i_s
    for i in range(i_p,i_k+1):
        if (i1 == i_s) or \
           ((i2 <= i_k) and \
            (d[i1] > d[i2])):
            p[i] = d[i2]
            i2 += 1
        else:
            p[i] = d[i1]
            i1 += 1
    for i in range(i_p,i_k+1):
        d[i] = p[i]

# Program główny
#---------------

print(" Sortowanie przez scalanie ")
print("---------------------------")
print("  (C)2026  Jerzy Wałaszek  ")
print()
print("Przed sortowaniem:")
print()
for i in range(n):
  print("%4d" % (d[i]), end="")
print()
print()

# Sortujemy

MergeSort(0, n-1)

# Wyświetlamy wynik sortowania

print("Po sortowaniu:")
print()
for i in range(n):
  print("%4d" % (d[i]), end="")
print()
print()
input("Naciśnij Enter...")
Wynik:
 Sortowanie przez scalanie 
---------------------------
  (C)2026  Jerzy Wałaszek  

Przed sortowaniem:

  93  70  61  77  76  46  11  87  27  52  58   9  62  94  33  24  32  41  73  28

Po sortowaniu:

   9  11  24  27  28  32  33  41  46  52  58  61  62  70  73  76  77  87  93  94

Naciśnij Enter...
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmmergesort">
      <h3 style="text-align: center">Sortowanie Przez Scalanie</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Sortuj" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Sortowanie Przez Scalanie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 20; // Liczebność zbioru.
var d = new Array(N);
var p = new Array(N);

// Procedura sortująca
//--------------------

function MergeSort(i_p, i_k)
{
  var i_s,i1,i2,i;

  i_s = Math.floor((i_p + i_k + 1) / 2);
  if(i_s - i_p > 1) MergeSort(i_p, i_s - 1);
  if(i_k - i_s > 0) MergeSort(i_s, i_k);
  i1 = i_p; i2 = i_s;
  for(i = i_p; i <= i_k; i++)
    p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];
  for(i = i_p; i <= i_k; i++) d[i] = p[i];
}

function main()
{
  var i,t;

  // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

  for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100);
  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  t += "<BR><BR>";

  // Sortujemy

  MergeSort(0,N-1);

  // Wyświetlamy wynik sortowania

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

Sortowanie Przez Scalanie

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...


do podrozdziału  do strony 

Podsumowanie

Cechy Algorytmu Sortowania Przez Scalanie
klasa złożoności obliczeniowej optymistyczna O(n·log(n))
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu NIE
Stabilność TAK

do podrozdziału  do strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.