Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
5 of 9 x86-64 version using basically the same algo.

x86-16 machine code function (sorting int8_t), 20 19 bytes

x86-64 machine code function (sorting int32_t) 21 bytes.

Thanks to @ped7g for the lodsb/cmp [si],al idea, and putting that together with a pointer increment / reset that I'd been looking at. Not needing al/ah lets us use nearly the same code for larger integers.

Sorts 8-bit signed integers in-place. (Unsigned is the same code size, just change the jge to a jae). Duplicates are not a problem. We swap using a 16-bit rotate by 8 (with a memory destination).

Bubble Sort sucks for performance, but I've read that it's one of the smallest to implement in machine code. This seems especially true when there are special tricks for swapping adjacent elements. This is pretty much its only advantage, but sometimes (in real life embedded systems) that's enough advantage to use it for very short lists.

I omitted the early termination on no swaps. I used Wikipedia's "optimized" loop which avoids looking at the last n − 1 items when running for the n-th time, so the outer loop counter is the upper bound for the inner loop.

NASM listing (nasm -l /dev/stdout)

 2 address  16-bit       bubblesort16_v2:
 3          machine      ;; inputs: pointer in ds:si,  size in in cx
 4          code         ;; requires: DF=0  (cld)
 5          bytes        ;; clobbers: al, cx=0
 6                       
 7 00000000 49               dec     cx          ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 8                       .outer:                 ; do{
 9 00000001 51               push    cx          ;   cx = inner loop counter = i=max_unsorted_idx
10                       .inner:                 ;   do{
11 00000002 AC               lodsb               ;     al = *p++
12 00000003 3804             cmp     [si],al     ;     compare with *p (new one)
13 00000005 7D04             jge     .noswap
14 00000007 C144FF08         rol     word [si-1], 8    ; swap
15                       .noswap:
16 0000000B E2F5             loop    .inner      ;   } while(i < size);
17 0000000D 59               pop     cx          ;  cx = outer loop counter
18 0000000E 29CE             sub     si,cx       ;  reset pointer to start of array
19 00000010 E2EF             loop    .outer      ; } while(--size);
20 00000012 C3               ret

22 00000013  size = 0x13 = 19 bytes.

push/pop of cx around the inner loop means it runs with cx = outer_cx down to 0.

Note that rol r/m16, imm8 is not an 8086 instruction, it was added later (186 or 286), but this isn't trying to be 8086 code, just 16-bit x86. If SSE4.1 would help, I'd use it.

A 32-bit version of this (still operating on 8-bit integers but with 32-bit pointers / counters) is 20 bytes (operand-size prefix on rol word [esi-1], 8)


Original version (NASM listing):

This version is more dependent on 16-bit mode / 8-bit integers: cmp ah, al to compare the two halves of a 16-bit load, because on x86 the upper and lower 8-bit halves of 16-bit registers are separately addressable.

16-bit addressing-modes indexed addressing modes don't add an extra byte. (32/64-bit code uses a SIB byte for [ebx + esi], because (almost) all combinations of registers can be used in addressing modes.)

Like the new version, we also benefit from 16-bit operand size not costing an operand-size prefix, because it's the default. 8-bit operand-size also doesn't require prefixes, those instructions have their own opcode. In 32 and 64-bit mode where we could use 8 and 16, or 16 and 32, or 32 and 64 operand size for compare and rotate, at least one of each pair requires an operand-size or REX prefix.

 3                       bubblesort16:
 4 address               ;; inputs: pointer in ds:bx,  size in in cx
 5          machine      ;; clobbers: ax, cx=0, si
 6          code
 7          bytes
 8 00000000 49               dec  cx       ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 9                       .outer:
10 00000001 31F6             xor  si, si         ; array index = si=0
12                       .inner:                 ; do{
13 00000003 8B00             mov  ax, [bx+si]    ; load arr[i] and arr[i+1]
15 00000005 38C4             cmp  ah, al
16 00000007 7D03             jge  .noswap
17 00000009 C10008           rol  word [bx+si], 8    ; swap
18                          .noswap:
20 0000000C 46               inc  si             ;   i++
21 0000000D 39CE             cmp  si, cx
22 0000000F 72F2             jb  .inner          ; } while(i < size);
23                       
24 00000011 E2EE             loop  .outer     ; while(--size);
25                       
26 00000013 C3               ret
 size = next address = 0x14 = 20 bytes.

For testing, I made a 32-bit version of this, and it does work (tested in gdb with display /d (char[5])buf to print out buf while stepping through the code to watch it sort). (Try it online doesn't have a debugger, and I didn't implement printing, but I did include a _start wrapper with test data you can watch in a debugger: Try it online!).

(I tested the new version locally, but I didn't update the TIO link. Source without NASM listing stuff on each line: https://pastebin.com/0VMzdUjj).


Performance

This implementation particularly sucks for performance (on modern x86 other than Atom), because every swap causes a store-forwarding failure on the next load (which partially overlaps it by 1 byte). This is mostly a latency penalty, not necessarily throughput, but it delays detection of branch mispredicts. It will also create long dependency chains on repeated swaps.

The updated version with byte loads for the compare avoids store-forwarding delays for the compare, but BubbleSort often moves one element pretty far. i.e. repeated swaps, and the overlapping rol word will be a problem there; out-of-order execution will have trouble hiding repeated store-forwarding stalls, even moreso than hiding repeated successful store->load forwarding. (e.g. 13 cycles vs. 5 or so on Haswell). Of course, using loop for the inner loop sucks on non-AMD CPUs.

See also: Stack Overflow: bubble sort for sorting string for a version of this with a similar implementation, but with an early-out when no swaps are needed. It uses xchg al, ah / mov [si], ax for swapping, which is 1 byte longer and causes a partial-register stall on some CPUs. (But it may still be better than memory-dst rotate, which needs to load the value again). My comment there has some suggestions...


x86-64 version, 21 bytes

Callable from C using the x86-64 System V calling convention as
void bubblesort64_int32(int dummy, int *array, int dummy, unsigned size);

32-bit operand size is the default (no prefixes), and 64-bit rotate is available with a REX prefix.

We can't use sub rsi, rcx because we need to subtract 4*rcx. Also, even a single 64-bit sub would take a REX prefix. (We could use the x32 ABI so pointers are in the low 32 bits...) But anyway, we can restore rsi to pointing at the start of the array using 2 bytes for push/pop around the inner loop.

The extra 2 bytes vs. 16-bit are:

  • dec ecx single-byte encoding not available in x86-64.
  • REX prefix needed for rol qword [rsi-4], 32

 1 address  machine      bubblesort64_int32:
 2          code         ;; inputs: pointer in rsi,  size in in ecx
 3          bytes        ;; clobbers: eax=smallest element, ecx=0
 4                       
 5 00000000 FFC9             dec     ecx          ; rcx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 6                       .outer:                 ; do{
 7 00000002 56               push    rsi
 8 00000003 51               push    rcx         ;   rcx = inner loop counter = i=max_unsorted_idx
 9                       .inner:                 ;   do{
10 00000004 AD               lodsd               ;     eax = *p++
11 00000005 3906             cmp     [rsi],eax   ;     compare with *p (new one)
12 00000007 7D05             jge     .noswap
13 00000009 48C146FC20       rol     qword [rsi-4], 32    ; swap
14                       .noswap:
15 0000000E E2F4             loop    .inner      ;   } while(--i);
16 00000010 59               pop     rcx         ;   rcx = outer loop counter = size
17 00000011 5E               pop     rsi         ;   reset pointer to start of array
18 00000012 E2EE             loop    .outer      ; } while(--size);
19 00000014 C3               ret
20                       
21 00000015 = size = 0x15 = 21 bytes

I tested this version (in GDB) using the this caller: Try it online!. You can run this it on TIO, but again no debugger or printing. Still, the _start that calls it exits with exit-status = smallest element.