Лекція 2

• Компіляція
• Дебаггінг
• Пам’ять
• Масиви
• Рядки
• Аргументи командного рядка
• Шифрування
• Коди виходу
• Сортування

Компіляція

• Ми почали курс з вивчення Scratch, а потім перейшли на мову програмування С.
• Нагадаємо, що ми пишемо вихідний код мовою програмування C, але ми маємо його спомпілювати на машинний код у двійковій системі, аби запустити на комп'ютері.
  • clang це компілятор, з яким ми вже познайомилися, а make – це утіліта, яка допомагає нам запускати clang автоматично.
  • Якщо б ми захотіли використати бібліотеку CS50 за допомогою #include <cs50.h>, та застосувати clang замість make, потрібно додати прапорець: clang hello.c -lcs50. Прапорець -l підключає файл cs50, який було встановлено у CS50 Sandbox.
• Компіляція вихідного коду на машинний відбувається у такі кроки:
  • препроцессінг
  • компіляція
  • збирання
  • компонування
• Препроцессінг складається з перегляду рядків, які починаються з #, як-от #include, перед тим, як виконувати все інше. Наприклад, #include <cs50.h> скаже clang знайти спочатку цей заголовковий файл, оскільки там міститься контент, який ми хочемо використати у нашій програмі. Потім, clang замінить вміст цих файлів в нашій програмі:

  ...
  string get_string(string prompt);
  int printf(const char *format, ...);
  ...
  int main(void)
  {
      string name = get_string("Name: ");
      printf("hello, %s\n", name);
  }
  

• Компіляція бере наш вихідний код на С та конвертує на код асемблера, який виглядає ось так:

  ...
  main:                 # @main
      .cfi_startproc
  # BB#0:
      pushq %rbp
  .Ltmp0:
      .cfi_def_cfa_offset 16
  .Ltmp1:
      .cfi_offset %rbp, -16
      movq %rsp, %rbp
  .Ltmp2:
      .cfi_def_cfa_register %rbp
      subq $16, %rsp
      xorl %eax, %eax
      movl %eax, %edi
      movabsq $.L.str, %rsi
      movb $0, %al
      callq get_string
      movabsq $.L.str.1, %rdi
      movq %rax, -8(%rbp)
      movq -8(%rbp), %rsi
      movb $0, %al
      callq printf
      ...
  

  • Це низькорівневі інструкції, тому краще зрозумілі центральному процессору, і вцілому працюють з байтами, а не з такими абстракціями, як назви змінних.
• Наступний крок – взяти код асемблера та перекласти його на інструкції у двійковій системі – це називається збирання.
• І наостанок потрібно все скомпонувати, коли вміст пов'язаних бібліотек, як cs50.c, фактично включаються до нашої програми у двійковому вигляді.

Дебаггінг

• Уявімо, ми написали програму buggy0:

  int main(void)
  {
      printf("hello, world\n")
  }
  

  • Ми бачимо помилку, коли намагаємось скомпілювати цю програму за допомогою make про те, що ми не додали заголовковий файл.
  • Ми можемо запустити help50 make buggy0, що врешті-решт повідомить нам про необхідність додати #include <stdio.h>, який містить printf.
  • Ми все зробили, а тепер бачимо ще одну помилку та розуміємо, що ми забули поставити крапку з комою в кінці рядка.
• Давайте розглянемо іншу програму:

  #include <stdio.h>
  
  int main(void)
  {
      for (int i = 0; i <= 10; i++)
      {
          printf("#\n");
      }
  }
  

  • Хм, ми думали, що буде лише 10 символів #, але їх вийшло 11. Якби ми не знали, в чому полягає проблема (оскільки наша програма працює так, як ми її написали), то могли б додати ще один рядок print на допомогу:

    #include <stdio.h>
    
    int main(void)
    {
        for (int i = 0; i <= 10; i++)
        {
            printf("i is %i\n", i);
            printf("#\n");
        }
    }
    

  • Тепер, ми бачимо, що i почалась з 0 і продовжувалась до 10, але ми повинні його зупинити на 9.
• Якби ми записали нашу програму без пробілів, як подано нижче, то вона все одно була б правильна:

  #include <stdio.h>
  
  int main(void)
  {
  for (int i = 0; i < 10; i++)
  {
  printf("i is %i\n", i);
  printf("#\n");
  }
  }
  

  • Однак, читати в такому вигляді складно, це поганий дизайн. Набагато легше буде побачити вкладеність, якщо ми використаємо відступи для циклів.
  • Ми можемо запустити style50 buggy2.c, і побачити рекомендації, що нам слід змінити.
• Отже, нагадаємо, ми маємо три інструменти, які допоможуть нам покращити код:
  • help50
  • printf
  • style50

Пам’ять

• В середині наших комп`ютерів містяться чіпи RAM, тобто оперативна пам'ять, що зберігає дані для короткочасного використання. Можна зберігати файли на жорсткому диску (або SSD) для довготривалого зберігання, але коли ми його відкриємо та будемо вносити зміни, все копіюється до RAM. Попри те, що обсяг RAM значно менший та вона є тимчасовою (поки не буде вимкнене живлення), вона значно швидша.
• Можна розглядати байти, які зберігаються в RAM, у вигляді сітки:
  • Насправді там розташовані мільйони або навіть мільярди байтів на кожному чіпі.
• У мові програмування С коли ми створюєму змінну типу char розміром в один байт, вона буде фізично збережена в одній із таких комірок у RAM. Ціле число на чотири байти займе чотири таких комірки.

Масиви

• У пам’яті ми можемо зберігати змінні послідовно, одна за одною. І в мові програмування С список збережених змінних, які розташовуються у суміжних комірках пам'яті, називається масивом.
• Виявляється, що з самими тільки масивами можна робити дуже цікаві речі.
• Розглянемо scores0.c:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Get scores from user
      int score1 = get_int("Score 1: ");
      int score2 = get_int("Score 2: ");
      int score3 = get_int("Score 3: ");
  
      // Generate first bar
      printf("Score 1: ");
      for (int i = 0; i < score1; i++)
      {
          printf("#");
      }
      printf("\n");
  
      // Generate second bar
      printf("Score 2: ");
      for (int i = 0; i < score2; i++)
      {
          printf("#");
      }
      printf("\n");
  
      // Generate third bar
      printf("Score 3: ");
      for (int i = 0; i < score3; i++)
      {
          printf("#");
      }
      printf("\n");
  }
  

  • Ми отримуємо 3 результати (scores) від користувача та виводимо графічне позначення для кожного з них.
  • Наші 3 цілих числа, score1, score2, та score3 будуть збережені десь у пам’яті.
• Ми можемо використати цикл, або почнемо розділяти на частини:

  #include <cs50.h>
  #include <stdio.h>
  
  void chart(int score);
  
  int main(void)
  {
      // Get scores from user
      int score1 = get_int("Score 1: ");
      int score2 = get_int("Score 2: ");
      int score3 = get_int("Score 3: ");
  
      // Chart first score
      printf("Score 1: ");
      chart(score1);
  
      // Chart second score
      printf("Score 2: ");
      chart(score2);
  
      // Chart third score
      printf("Score 3: ");
      chart(score3);
  }
  
  // Generate bar
  void chart(int score)
  {
      // Output one hash per point
      for (int i = 0; i < score; i++)
      {
          printf("#");
      }
      printf("\n");
  }
  

  • Тепер маємо функцію chart яка буде виводити кожен результат.
  • Пам'ятайте, що нам потрібно мати на початку прототип, void chart(int score);. Ми моглиб мати всю функцію chart вгорі перед її використанням, але врешті наша функція main буде спускатись все нижче і шукати її буде все складніше.
• За допомогою масивів ми можемо зібрати результати в циклі, а потім одержати до них доступ, також в циклі:

  // Generates a bar chart of three scores using an array
  
  #include <cs50.h>
  #include <stdio.h>
  
  void chart(int score);
  
  int main(void)
  {
      // Get scores from user
      int scores[3];
      for (int i = 0; i < 3; i++)
      {
          scores[i] = get_int("Score %i: ", i + 1);
      }
  
      // Chart scores
      for (int i = 0; i < 3; i++)
      {
          printf("Score %i: ", i + 1);
          chart(scores[i]);
      }
  }
  
  // Generate bar
  void chart(int score)
  {
      // Output one hash per point
      for (int i = 0; i < score; i++)
      {
          printf("#");
      }
      printf("\n");
  }
  

  • Зверніть увагу, що ми застосовуємо int scores[3] для ініціалізації масиву з трьома цілими числами. Потім ми використовуємо scores[i] = ..., щоб зберегти значення в цьому масиві, використовуючи для цього індекс i від 0 до 2 (оскільки в нас три елементи).
  • Після цього ми використовуємо scores[i] для доступу до усіх значень в масиві за кожним індексом.
• У нас повторюється число 3 кілька разів, тому ми можемо виокремити його у константу, тобто число, яке ми можемо один раз задати й використовувати глобально:

  #include <cs50.h>
  #include <stdio.h>
  
  const int COUNT = 3;
  
  void chart(int score);
  
  int main(void)
  {
      // Get scores from user
      int scores[COUNT];
      for (int i = 0; i < COUNT; i++)
      {
          scores[i] = get_int("Score %i: ", i + 1);
      }
  
      // Chart scores
      for (int i = 0; i < COUNT; i++)
      {
          printf("Score %i: ", i + 1);
          chart(scores[i]);
      }
  }
  
  // Generate bar
  void chart(int score)
  {
      // Output one hash per point
      for (int i = 0; i < score; i++)
      {
          printf("#");
      }
      printf("\n");
  }
  

  • На початку ми використовуємо ключове слово const щоб визначити, що це незмінне значення. Його можна використовувати по всьому коду, і якщо ми захочемо щось змінити, достатньо змінити лише один раз. Врешті, назва COUNT написана великими літерами, щоб показати, що це константа (за домовленістю).
• Ми можемо за допомогою функції chart вивести всі результати, а не по одному стовпчику за раз:

  #include <cs50.h>
  #include <math.h>
  #include <stdio.h>
  
  const int COUNT = 3;
  
  void chart(int count, int scores[]);
  
  int main(void)
  {
      // Get scores from user
      int scores[COUNT];
      for (int i = 0; i < COUNT; i++)
      {
          scores[i] = get_int("Score %i: ", i + 1);
      }
  
      // Chart scores
      chart(COUNT, scores);
  }
  
  // Generate bars
  void chart(int count, int scores[])
  {
      // Output one hash per point
      for (int i = 0; i < count; i++)
      {
          for (int j = 0; j < scores[i]; j++)
          {
              printf("#");
          }
          printf("\n");
      }
  }
  

  • Передавши весь масив scores та кількість результатів count які ми хочемо вивести, ми можемо використати функцію chart для ітерування крізь масив scores. Фактично, chart наскільки великим є масив scores, тож ми обов'язково маємо передавати й count.

Рядки

• Рядки – це насправді просто масиви символів. Це можна побачити у string0.c:

  #include <cs50.h>
  #include <stdio.h>
  #include <string.h>
  
  int main(void)
  {
      string s = get_string("Input:  ");
      printf("Output: ");
      for (int i = 0; i < strlen(s); i++)
      {
          printf("%c\n", s[i]);
      }
  }
  

  • Спочатку нам знадобиться нова бібліотека, string.h, для strlen, що показує нам довжину рядка. Далі ми використовуємо той же синтаксис для доступу до елементів масиву, s[i], аби вести окремі символи рядка s.
• Ми можемо покращити дизайн нашої програми. string0 була не надто ефективна, оскільки перевіряємо довжину рядка після введення кожного символу, в нашій умові. Проте оскільки довжина рядка не змінюється, то ми можемо перевіряти її лише один раз:

  #include <cs50.h>
  #include <stdio.h>
  #include <string.h>
  
  int main(void)
  {
      string s = get_string("Input: ");
      printf("Output:\n");
      for (int i = 0, n = strlen(s); i < n; i++)
      {
          printf("%c\n", s[i]);
      }
  }
  

  • Зараз, на початку нашого циклу, ми ініціалізуємо дві змінні i та n та записуємо довжину рядка у n. Далі ми можемо щоразу перевіряти значення без вираховування довжини рядка.
  • n буде доступна виключно в межах циклу for хоча ми можемо ініціалізувати її і поза ним, якщо нам потрібно буде її повторне використання.
• Коли рядок зберігається у пам’яті, кожен символ розміщується в одному байті в таблиці байтів. Десь, наприклад, слово Zamyla збережено у 6 байтах. Але нам потрібен ще один байт, для позначення кінця рядка:
  • Байт пам'яті, де збережено перший символ рядка, Z, позначено як s, оскільки ми назвали наш рядок s у коді вище. Далі, після останнього символу, a, ми маємо один байт з усіма 0 для позначення кінця рядку. І ьайт з усіма 0 називається нульовим символом, який можна також позначати як \0.
• Якби ми хотіли написати власну версію strlen, наприклад, то нам треба знати наступне:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Prompt for user's name
      string s = get_string("Name: ");
  
      // Count number of characters up until '\0' (aka NUL)
      int n = 0;
      while (s[n] != '\0')
      {
          n++;
      }
      printf("%i\n", n);
  }
  

  • Тут ми перебираємо кожен символ рядка s, використовуючи той же синтаксис, що й для доступу до елементів масивів, і ми інкрементуємо лічильник, n, поки символ не дорівнюватиме нульовому символу, \0. Якщо він дорівнює, значить, ми в кінці рядка й можемо вивести значення n.
• Оскільки ми знаємо, що кожен символ має числове, ASCII значення, то можна вивести й таке:

  #include <cs50.h>
  #include <stdio.h>
  #include <string.h>
  
  int main(void)
  {
      string s = get_string("String: ");
      for (int i = 0; i < strlen(s); i++)
      {
          int c = (int) s[i];
          printf("%c %i\n", s[i], c);
      }
  }
  

  • За допомогою (int) s[i], wми беремо значення s[i] та перетворюємо символьний тип на цілочисельний. Після цього ми можемо вивести як символи, так і їхні числові значення.
  • Технічно ми навіть можемо зробити printf("%c %i\n", s[i], s[i]);, а printf розпізнає значення s[i] як ціле число.
• Тепер ми можемо поєднати те, що ми розглянули, аби створити програму, яка замінює маленькі літери на великі:

  #include <cs50.h>
  #include <stdio.h>
  #include <string.h>
  
  int main(void)
  {
      string s = get_string("Before: ");
      printf("After:  ");
      for (int i = 0, n = strlen(s); i < n; i++)
      {
          if (s[i] >= 'a' && s[i] <= 'z')
          {
              printf("%c", s[i] - ('a' - 'A'));
          }
          else
          {
              printf("%c", s[i]);
          }
      }
      printf("\n");
  }
  

  • Спочатку ми отримуємо рядок s. Тоді, для кожного символу в рядку, якщо він в нижньому регістрі (його значення знаходиться між a та z), ми конвертуємо його на велику літеру. В іншому випадку, ми його просто виводимо.
  • Ми можемо перетворити малі літери у великі шляхом віднімання різниці між малою a та великою A. (Ми знаємо, що у малих літер більші значення, тому можна відняти різницю між ними та перетворити малі літери на великі.)
• Також є функції з бібліотек, які ми можемо використати для досягнення того ж ефекту:

  #include <cs50.h>
  #include <ctype.h>
  #include <stdio.h>
  #include <string.h>
  
  int main(void)
  {
      string s = get_string("Before: ");
      printf("After:  ");
      for (int i = 0, n = strlen(s); i < n; i++)
      {
          if (islower(s[i]))
          {
              printf("%c", toupper(s[i]));
          }
          else
          {
              printf("%c", s[i]);
          }
      }
      printf("\n");
  }
  

  • Можна використати функції islower() та toupper() з бібліотеки ctype. (Про це можна довідатись виключно з документації до бібліотеки, яку інші люди написали задовго до нас.)
  • Ми можемо використовувати програму командного рядка, man, щоб прочитати інструкцію з використання інших програм, якщо така існує. Наприклад, ми можемо запустити man toupper для перегляду документації для цієї функції. Ми побачимо, що toupper повертає символ таким, яким він є, якщо він не написаний маленькими літерами, тож отримаємо:

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        printf("%c", toupper(s[i]));
    }
    

Аргументи командного рядка

• Ми використовували такі програми як make та clang, які приймають додаткові слова після своєї назви в командному рядку. Але насправді, наші програми також можуть приймати аргументи командного рядка.
• У argv0.c, ми змінюємо вигляд нашої функції main:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(int argc, string argv[])
  {
      if (argc == 2)
      {
          printf("hello, %s\n", argv[1]);
      }
      else
      {
          printf("hello, world\n");
      }
  }
  

  • argc та argv - це дві змінні, які одержить функція main коли ми запустимо нашу програму з командного рядка. argcargc – це лічильник аргументів, тобто їх кількість, а argv - масив рядків, що є аргументами. Найперший аргумент, argv[0], буде назвою нашої програми (найперше надруковане слово, наприклад, ./hello). У цьому прикладі ми перевіримо, чи маємо ми два аргументи, і, якщо так, виведемо другий.
• Ми можемо вивести кожен аргумент, один за одним:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(int argc, string argv[])
  {
      for (int i = 0; i < argc; i++)
      {
          printf("%s\n", argv[i]);
      }
  }
  

• Ми також можемо вивести кожен символ кожного аргументу:

  #include <cs50.h>
  #include <stdio.h>
  #include <string.h>
  
  int main(int argc, string argv[])
  {
      for (int i = 0; i < argc; i++)
      {
          for (int j = 0, n = strlen(argv[i]); j < n; j++)
          {
              printf("%c\n", argv[i][j]);
          }
          printf("\n");
      }
  }
  

  • За допомогою argv[i], ми отримуємо поточний аргумент із масиву аргументів, а з argv[i][j], символ з цього рядка.

Шифрування

• Якби ми хотіли надіслати комусь повідомлення, ми б, можливо, захотіли його зашифрувати, тобто певним чином змінити повідомлення, щоб іншим було важко його прочитати. Оригінальний текст тоді ми назвемо звичайний текст, а текст після шифрування - зашифрований текст.
• Таке повідомлення, як HI! може бути перетворене в ASCII, 72 73 33. Проте, кожен може з легкістю виконати цю дію і в зворотному порядку.
• Розглянемо приклади шифрів з історії, починаючи ще з Першої світової війни, до поеми про поїздку Пола Рівера.
• Загалом шифрування потребує не тільки самого тексту на вхід, а й додаткової інформації. Потрібен ключ, іноді це просто секретне число. Відкритий текст може бути зашифрований та розшифрований за допомогою ключа за певним алгоритмом.
• Наприклад, якщо ми хочемо надіслати текст I L O V E Y O U, ми спочатку можемо його перетворити на ASCII: 73 76 79 86 69 89 79 85. Тоді, ми можемо зашифрувати його ключем 1 простим алгоритмом, де ми лише додаємо ключ до значення кожного елемента: 74 77 80 87 70 90 80 86. Після цього, якщо хтось перетворить ASCII назад в текст, то отримає J M P W F Z P V. Для розшифровки потрібно буде здогадатися значення кожної букви, методом спроб та поразок, але напевне знати без ключа неможливо. Цей алгоритм відомий під назвою шифр Цезаря.

Коди виходу

• Виявляється, що ми можемо вказувати на помилки в нашій програмі, повертаючи значення з функції main:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(int argc, string argv[])
  {
      if (argc != 2)
      {
          printf("missing command-line argument\n");
          return 1;
      }
      printf("hello, %s\n", argv[1]);
      return 0;
  }
  

  • Значення, що повертається main в нашій програмі, називається кодом виходу, і ми можемо це побачити в командному рядку. Якщо ми запустимо нашу програму через ./exit, можемо потім набрати echo $?, яка виведе повернене останньою програмою значення.
  • Коли ми почнемо писати складніші прошрами, то такі коди виходу допоможуть нам вчасно зрозуміти, що пішло не так, навіть якщо вони невидимі або незрозумілі для користувача.

Сортування

• З масивами ми можемо розв’язувати значно цікавіші задачі. Наприклад, ми можемо розглядати масиви як шафки, за дверима кожної з яких знаходиться якесь значення – ціле число чи символ. До того ж, комп’ютер здатний розглядати одну шафку або значення за раз.
• Якби ми мали список чисел та хотіли знайти в ньому певне число, найкраще що можна зробити, це переглянути його значення один за одним або в довільному порядку.
• Проте якби ми знали, що список був відсортований, то спочатку могли б поглянути в його середину і, відповідно, потім рухались би вліво або вправо.
• Разом з добровольцями ми розглянули, як можна відсортувати список.
• Наші добровольці почали у такому довільному порядку:

  6 5 1 3 7 8 4 2
  

• Ми поглянули на перші два числа та переставили їх, щоб вони були у правильному порядку:

  5 6 1 3 7 8 4 2
  

• • Потім ми розглянули наступну пару чисел, 6 та 1, та переставили їх місцями:

  5 1 6 3 7 8 4 2
  

• Ми повторюємо цю дію, поки найбільше число після першого проходу не опиниться з правого боку в кінці рядка:

  5 1 6 3 7 4 2 8
  

  • (У лекції, цифра 1 була випадково поставлена занадто далеко!)
• Ми повторюємо і щоразу, коли ми робимо один прохід, наступне найбільше число стає справа в кінці:

  1 5 3 6 4 2 7 8
  

• Нарешті наш список повністю відсортований. Спочатку ми порівняли 7 пар чисел, потім – 6 пар.
• Ми повторно перемішали числа:

  2 4 8 5 7 1 3 6
  

• І цього разу ми шукали найменше число в списку та переміщували його в лівий бік:

  1 4 8 5 7 2 3 6
  1 2 8 5 7 4 3 6
  1 2 3 5 7 4 8 6
  

  • Щоразу ми обирали найменше число і переставляли його з числом, яке знаходиться зліва у невідсортованій частині списку.
• За допомогою цього алгоритму ми все ще проглядаємо список n - 1 разів, де n кількість людей, та нам потрібно порівняти кожне число, з найменшим.
• Давайте спробуємо розв’язати це формальніше. Перший алгоритм, сортування бульбашкою, складається з порівнювання пар чисел, що знаходяться безпосередньо одна біля одної, поки найбільше число буде знаходитися справа в кінці. Ми можемо це записати в псевдокоді:

  повторити поки не залишиться пробілів
      для i від 0 до n-2
          якщо i-ий та i+1-ий елементи не відсортовані
              поміняти їх місцями
  

• А сортування вибором може виглядати ось так:

  для i від 0 до n-1
      знайти найменший елемент між i-им та n-1-им
      поміняти місцями найменший та i-ий елементи
  

• Для першої перестановки нам потрібно зробити n - 1 порівнянь, щоб знайти найменше число. В кожному наступному проході ми зробили меншу кількість порівнянь, оскільки ми вже перемістили деякі цифри ліворуч:

  (n – 1) + (n – 2) + ... + 1
  n(n – 1)/2
  (n^2 – n)/2
  n^2 / 2 – n/2
  

  • Кожен наступний рядок стає простіше, і врешті ми отримуємо n^2 / 2 – n/2 як кількість порівнянь, які треба виконати. В комп'ютерних науках ми використовуємо O, нотація велике O для більшого спрощення, щоб сказати, що наш алгоритм має O(n^2) кроків, “порядку n в квадраті”. Це через те, що з ростом n лише n^2 має значення.
  • Наприклад, якщо б n був 1,000,000, ми б отримали:

    n^2 / 2 – n/2
    1,000,000^2 / 2 – 1,000,000/2
    500,000,000,000 – 500,000
    499,999,500,000
    

    • що є того ж порядку, що й n².
• • Виявляється, що є інші поширені порядки величин складності:
  • O(n²)
  • O(n log n)
  • O(n)
  • O(log n)
  • O(1)
• Пошук в телефонній книзі по одній сторінці за раз має тривалість роботи O(n), оскільки для кожної сторінки потрібна одна дія. Використання бінарного пошуку могло б мати тривалість роботи O(log n), оскільки ми б розділяли задачу навпіл щоразу.
• Давайте візьмемо інший масив чисел, але цього разу використаємо пустий масив такого ж розміру, як наш робочий:

  4 2 7 5 6 8 3 1
  _ _ _ _ _ _ _ _
  

• Оскільки у нас 8 чисел, давайте поглянемо на першу половину, тобто на перші 4. Відсортуємо це рекурсивно, подивимося на ліву половину. Маючи 2 числа, 4 2, дивимося на ліву половину (відсортовану), та праву (відсортовану), та об'єднаємо їх, відсортувавши: 2 4. Ми перенесемо їх у наш другий масив:

  _ _ 7 5 6 8 3 1
  2 4 _ _ _ _ _ _
  

• Повторимо це для правої частини першої половини:

  _ _ | _ _ 6 8 3 1
  2 4 | 5 7 _ _ _ _
  

• потім об'єднаємо ці половини, щоб отримати відсортовану ліву частину:

  _ _ _ _ 6 8 3 1
  _ _ _ _ _ _ _ _
  2 4 5 7 _ _ _ _
  

• Повторимо те саме для правої частини:

  _ _ _ _ | _ _ _ _
  _ _ _ _ | _ _ _ _
  2 4 5 7 | 1 3 6 8
  

• Тепер можемо об'єднати обидві половини:

  _ _ _ _ _ _ _ _
  _ _ _ _ _ _ _ _
  _ _ _ _ _ _ _ _
  1 2 3 4 5 6 7 8
  

• Кожне число було переставлене тричі, через те що ми поділили 8 на 2 три рази, або log n раз. Тому цей алгоритм займає O(n log n) часу щоб відсортувати список.
• Розгляньте приклад Sorting Algorithms Animations та відео What different sorting algorithms sound like.